树状数组及其应用双语版

树状数组及其应用BinaryIndexedTree

引例【题目描述】输入一个数列A1,A2….An(1<=N<=100000)，在数列上进行M(1<=M<=100000)次操作，操作有以下两种：格式为CIX，其中C为字符“C”，I和X(1<=I<=N,|X|<=10000)都是整数，表示把把a[I]改为X格式为QLR，其中Q为字符“Q”，L和R表示询问区间为[L,R](1<=L<=R<=N)，表示询问A[L]+…+A[R]的值。【输入】第一行输入N(1<=N<=100000)，表述数列的长度，接下来N行，每行一个整数(绝对值不超过10000)依次输入每个数；接下来输入一个整数M(1<=M<=100000)，表示操作数量，接下来M行，每行为CIX或者QLR。【输出】对于每个QLR的操作输出答案。如果直接用数组模拟，那么修改是O(1),查询是O(n),如果维护另一个数组b[i]，表示a[1]到a[i]的和，那么修改是O(n),查询时O(1)。一个程序的时间复杂度取决于其中最大的时间复杂度。树状数组的目的就是平摊修改和查询的时间，使复杂度由O(n)降到O(lgn)。树状数组是一种数据结构，这种结构能让我们的程序变得高效，数据结构大多数时候是为了优化算法而用的。树状数组对于原数组a维护另一个数组c，c[i]表示sum(a[j]),i-lowbit(i)+1<=j<=i,其中lowbit(i)表示取出i二进制表示中最右边的1。例如lowbit(6)=lowbit(110)2=(10)2=2所以c[6]=a[5]+a[6];lowbit(4)=lowbit(100)2=(100)2=4

c[4]=a[1]+a[2]+a[3]+a[4]lowbit[5]=lowbit(101)2=(1)2=1;c[5]=a[5]其比较简单的算法为

lowbit(i)=i&(-i)

或i&(i^(i-1))lowbit(i)=iand(-i)

或iand(ixor(i-1))结论1、节点i的父亲节点为i+lowbit(i)2、节点i的最近不相交前驱为i-lowbit(i)3、若需改变a[i]，则c[i]、c[i+lowbit(i)]、c[i+lowbit(i)+lowbit(i+lowbit(i)]……一直加到上限，就是需要改变的c数组中的元素。

4、若需查询s[i]，则c[i]、c[i-lowbit(i)]、c[i-lowbit(i)-lowbit(i-lowbit(i))]……就是需要累加的c数组中的元素。

5、以上的修改和查询都是log2(n)级别的。Procedureadd(k,delt);Beginwhilek<=limitdobegin

C[k]:=C[k]+delta;k:=k+lowbit(k);End;End;由此我们可以得出修改与查询操作voidadd(k,delt){

while(k<=limit){

c[k]+=delt;k+=lowbit(k);}}Functiongetsum(k:integer):integer;Var

t:integer;Begint:=0;whilek>0dobegint:=t+c[k];k:=k-lowbit(k);end;

getsum:=t;End;当要查询a[i..j]累加和时，可以先求出a[1..j],a[1..i-1]，然后相减int

getsum(intk){

intt=0;while(k>0){t+=c[k];k-=lowbit[k];}returnt;}在实际应用中，通常不需要保存原数组a，只保存数组c即可。因此，树状数组几乎不需要附加空间。通过上面的学习可以看出：树状数组所能支持的操作是修改点值、查询区间和。与线段树和其他数据结构相比，树状数组代码简单，常数小，在其能解决范围内或经过转化使用树状数组，可以极大的降低编程复杂度，使代码清晰，简洁优秀的数据结构！例题、Stars(ural1028)题目大意平面中有N个点，对于每个点(x,y)，要求输出在其左下方（包括正左正下）点的个数。N<=100000;x,y<=maxlongint枚举？代码简单，时间复杂度达到O(n2)有没有代码简单、时间复杂度低的方法？此题有效的算法很多，树状数组可以简洁快速的解决此问题。如何构建树状数组？如何处理巨大的(x,y)？如何处理“左下方”？首先，离散化y坐标，然后按x坐标从小到大排序，x相同则y坐标由小到大，从左到右扫描每个点，这样可以保证已经插入树状数组的点都在左侧或正下侧。我们只需寻找有多少点位于当前点下方，很容易想到树状数组。处理完当前点后，将其按y坐标插入树状数组，即让a[y]加1此题是树状数组的经典应用首先离散化坐标使数据范围减小，为使用树状数组创造了条件按横坐标排序，使得原题中“左下方”两个条件限制转化为“下方”这一单一限制可以轻松运用树状数组解决现在，我们将树状数组推广到二维

先看一道神奇的题目2、Superbrother打鼹鼠(vijos1512)题目大意给定一个n*n的正方形区域，左上角为(0,0),右下角为(n-1,n-1)，初始所有整点权值为0。任意时刻有两种操作：1、在一个整点处权值加K2、询问一个矩形内整点权值和N<=1024这道题目是神牛Superbrother原创，很难！此题可以用二维线段树或二维树状数组解决。二维树状数组的代码与一维及其相似。Functiongetsum(x,y):integer;(求出矩阵(1,1)~(x,y)点值和)Var

z,t:longint;Begint:=0;whilex>0dobeginz:=y;whilez>0dobegint:=t+c[x,z];z:=z-lowbit(z);end;x:=x-lowbit(x);end;

getsum:=t;End;

对于询问(x1,y1)-(x2,y2)，

ans=getsum(x2,y2)-getsum(x2,y1-1)-getsum(x1-1,y2)+getsum(x1-1,x2-1);注意!树状数组下标必须从1开始Superbrother神牛到此，我们已经学习完树状数组的基本内容。树状数组的应用非常广泛，变形极多，灵活性强，很多题目经过一系列转化后可以使用树状数组解决。下面，我将通过其他几个例题介绍如何通过有效的转化使用树状数组解题。3、Cows(pku2481)题目大意有n头牛，每头牛喜欢吃[s[i],e[i]]这个区间的草。如果对于i、j两头牛，s[i]<=s[j]且e[j]<=s[i]且等号最多成立一个，那么i比j强。输出每头牛比多少头牛强。N,s,e<=10^5样例输入样例输出

3100120334此题条件简单，但并不直观将区间坐标化，我们发现，对于每头牛，要求的就是其左上方的牛的个数。同stars，注意判断点重合的情况4、逆序对题目大意给定一个序列a[1]..a[n]，对于任意i,j,如果i<j并且a[i]>a[j]，我们说这是一个逆序对。你的任务是输出逆序对的个数N<=100000a[i]<=maxlongint此题直接枚举同样需要n2的时间此题同样解法较多，可以使用分治法类似归并排序，也可以使用树状数组。此题和stars同样有两个限制:“i<j并且a[i]>a[j]”应用同一思路，顺序扫描，将其转化为一个限制——a[i]>a[j]。首先对a数组离散化按顺序扫描，只需找到有多少比a[i]大的数已经出现过。这可以用树状数组维护。初始时，数组全为0。每次扫描到a[i]，用树状数组求出a[i]+1～max中出现过多少个数，然后将a[i]插入树状数组。例如n=5,输入1006723首先离散化，输入变为53412顺序扫描i12345100000例如n=5,输入1006723首先离散化，输入变为53412顺序扫描i12345200001例如n=5,输入1006723首先离散化，输入变为53412顺序扫描i12345300101例如n=5,输入1006723首先离散化，输入变为53412顺序扫描i12345400111例如n=5,输入1006723首先离散化，输入变为53412顺序扫描i12345510111小结以上几道例题比较简单，属于树状数组的基础用法，主要起到数据结构的作用，用来对数据进行快速的存储和处理。树状数组与其他数据结构相比，最大的特点就是代码简单，常数小，从而得到广泛的应用。树状数组的基本操作就是两个，修改某个元素的值，求区间累加和。括号括号表示法是运用树状数组解题的重要方法之一。应用括号表示，可以将一部分修改区间、查询点值的题目转化为修改点值、查询区间，从而可以使用树状数组。5、Superbrother种树实验中学东校坐落在济南市郭店镇。为了迎全运，树新风，需要在一条长为n的道路上种若干种树。道路表示为[0,n]，共n+1个点。由于经费紧张，教导处将这个重任交给了信息组头号神牛Superbrother，希望他合理分配树木，使道路更加漂亮。Superbrother经过研究，制定了一套详细的计划。计划可以描述为若干个操作，每个操作在[l,r]中所有点种一棵颜色特殊的树。教导处随时都会检查，方式为给定一个点，要求他回答这个点一共种过多少种不同的树。输入第一行为n,m

以下m行，可能是一次种树，也可能是一次询问。此题与前面几题不同，要求修改一段区间的值，询问一个点的值。使用线段树可以轻松处理。有没有更简单、快速的方法？利用括号，转化为树状数组＜＞要将修改区间操作转化为修改点的操作，只有在区间端点做文章。每次修改区间，便在区间两端加括号。这样，每次询问时只需要输出从0～这个点中左括号数-右括号数。＜＞＜＜＜＞＞＞具体的，对于每个修改操作[l,r]，将树状数组中c[l]+1,c[r+1]-1。对于询问操作t，输出getsum(t)。时间复杂度O(mlgn)＜＞＜＜＜＞＞＞6、Matrix(pku2155)题目大意给定一个n*n的01矩阵，初始全部为0。要求维护两个操作：1、Cx1y1x2y2，子矩阵(x1,y1)~(x2,y2)中数值全部取反2、Qxy，询问点(x,y)的值样例输入样例输出

2101C21220Q220C21211Q11C1121C1212C1122Q11C1121Q21此题是区间求反问题，而树状数组所维护的是区间和问题。如何转化？注意到所求为一个点的值，而点值只与求反操作次数有关首先考虑一维情况原问题变为：对于一个数列，每次对一段区间取反，询问一个点的值。由于一个点的值只与取反次数有关，所以我们记录每个点的取反次数。树状数组支持的操作是修改一个点的值，查询一段区间的和。而此题恰恰相反。如何改变树状数组的意义？

括号每次对一段区间(a,b)取反，可以看成加了一对括号。每次询问只需求出从1到k中左括号-右括号,即为点k修改的次数数组c[i]记录1~i中左括号-右括号的值。每次修改(a,b),c[a]加1，c[b+1]减1。这样，每次询问求出c[k]，判断奇偶即可。如何推广到二维？查询操作不变，对于每次修改操作(x1,y1)-(x2,y2)，我们仿照一维情形加“括号”。具体的c[x1,y1]+1,c[x2+1,y2+1]+1c[x1,y2+1]-1,c[x2+1,y1]-17、密码机题目大意有一个初始为空的序列。维护三种命令：1、ADD<Number>把Number加到数列最后2、REMOVE<Number>在数列中找到等于<Number>的数，删除3、xorbetween<Number1>and<Number2>对于数列中所有在[Number1,Number2]中的数异或并输出结果加入的数不超过20000，询问次数<=60000算法一：直接处理对于Add操作，直接将Number添加到数组尾端。O(1)对于Remove操作，直接查询并删除。O(n)对于Xor操作，枚举每一个元素。O(n)时间复杂度O(T*n)小优化Xor操作即按位异或.1xor1=0.1xor0=1.0xor0=1.对于delete操作，我们其实可以将其视为Add操作。因为axora=0.axor0=a，所以delete(Number)将相当于add(Number)这样Delete操作复杂度降到(1)算法的瓶颈在于询问操作由于询问操作可能达到O(n)，所以如果要降低时间复杂度，就不能枚举全部符合条件的数然后异或，只能利用某些方法一起计算。观察输入，我们发现加入的数不超过20000，如何利用这个条件？树状数组!算法二：树状数组将Add操作和Delete操作看成Add，把树状数组操作中加法改成xor。可以证明，这种方法可以得到正确的结果。对于询问[l,r]，因为axora=0,axor0=a，可以直接输出get(r)xorget(l-1)每个操作复杂度均为logn，总时间复杂度为O(Tlogn)8、Jason911追MMSsfz神牛颇多，但最会追MM的当属Jason911。这一天jason911发现n个MM，jason911非常高兴，很想让她们全当自己GF。但是她发现如果如果找太多GF会让她们很不满意，于是他决定只找5个MM当GF。MM们按顺序排成1～n，各有一个魅力值。Jason911决定，他要使找到GF的魅力值严格递增，这样才能心情愉快。他想知道一共有多少种选法例如有7个MM，魅力值分别为{2,1,3,4,5,7,6}。合法的取法有4种，分别为{1,3,4,5,6},{2,3,4,5,6},{1,3,4,5,7}和{2,3,4,5,7}。MM最多有50000个对于一般的LIS，可以使用动态规划，运用二分可以达到(nlogn)。本题要求方案数，朴素的DP可以另维护一个数组g[i,j]表示表示以i为结尾、长度为j的上升子序列的种数。能否仍用二分，同时求出方案数？比较困难考虑使用树状数组记录次数和长度此题要求LIS长度为5，即可分为5个阶段。分别为1～5，各开一个树状数组，记录方案数。具体的，扫描到每个MM时，首先将其加入到第一个树状数组，然后j从1循环到4，判断能够找到多少魅力值小于她的MM，并加入到下一个树状数组。长度12345671+123452,1,3,4,5,7,6ij长度12345671+1123452,1,3,4,5,7,6ij长度1234567111+12+23452,1,3,4,5,7,6ij长度12345671111+122+33452,1,3,4,5,7,6ij长度1234567111112233+2452,1,3,4,5,7,6ij长度123456711111+1223+432452,1,3,4,5,7,6ij长度1234567111111223432+5452,1,3,4,5,7,6ij长度123456711111122343254+252,1,3,4,5,7,6ij长度1234567111111+12234+53254252,1,3,4,5,7,6ij长度1234567111111122345325+94252,1,3,4,5,7,6ij长度1234567111111122345325942+752,1,3,4,5,7,6ij长度123456711111112234532594275+22,1,3,4,5,7,6ij长度1234567111111+112234+553259427522,1,3,4,5,7,6ij长度123456711111111223455325+99427522,1,3,4,5,7,6ij长度1234567111111112234553259942+77522,1,3,4,5,7,6ij长度1234567111111112234553259942775+222,1,3,4,5,7,6ij长度1234567111111112234553259942775222,1,3,4,5,7,6ij答案是4小结利用括号的思想，树状数组可以在一定程度上解决修改区间、查询点值的功能。对于一些状态阶段、要求统计方案数的题目，常使用多棵树状数组分阶段记录，并在阶段之间转移。9、Japan(pku3067)题目大意给定一个二分图，左边M个点，右边N个点，从上倒下分别为1,2,3……中间有一些边连接两端的点，任意三条边不共点。求出总交点个数M,N<=1000,k<=100000样例输入

344(n,m,k)14233231样例输出5如何运用点的有序性？相交的实质？(x1,y1),(x2,y2)两边相交的条件:x1<x2,y1>y2应用同样的思路，转化为一个条件！按左端点对边排序（如果相同则右端点小的在前）。扫描每一条边，这样保证了已经加入边的左端点在当前边上方。这样只需查找有多少条已经扫描过的边的右端点在当前边下方。如图，当扫描到红色边时，我们需要查找的区域即为3,4，各有一条边形成相交由此，问题变成了改变点的值，询问一个区间内点值和

树状数组！

树状数组求最值问：树状数组能求最值么？前ｉ项的最值是可以求的。只要把求和改成ｍａｘ就可以了。但是求［ｌｅｆｔ，ｒｉｇｈｔ］之间的最值能求么？思考一下！好像无从下手。我们先讨论先构造，只查询，不修改的那种模式。修改值还是和求和一样的voidInit(intn){

for(inti=1;i<=n;i++)

for(intj=i;j<=n;j+=Lowbit(j))

c[j]=MAX(c[j],num[i]);

}这种方法在每次调用该函数前都必须对数组进行初始化，这样对于数据范围比较大的时候不是很优美,这样我们可以改为：voidInit(intn){

for(inti=1;i<=n;i++){

c[i]=num[i];

for(intj=1;j<Lowbit(i);j<<=1)

c[i]=MAX(c[i],c[i-j]