树状数组及其应用双语版-文档资料

1、1树状数组及其应用树状数组及其应用Binary Indexed Tree 2 引例引例【题目描述】输入一个数列A1,A2.An(1=N=100000)，在数列上进行M(1=M=100000)次操作，操作有以下两种：格式为C I X，其中C为字符“C”，I和X(1=I=N,|X|=10000)都是整数，表示把把aI改为X格式为Q L R，其中Q为字符“Q”，L和R表示询问区间为L,R(1=L=R=N)，表示询问AL+AR的值。【输入】第一行输入N(1=N=100000)，表述数列的长度，接下来N行，每行一个整数(绝对值不超过10000)依次输入每个数；接下来输入一个整数M(1=M=100000)

2、，表示操作数量，接下来M行，每行为C I X或者Q L R。【输出】对于每个Q L R 的操作输出答案。3 如果直接用数组模拟，那么修改是O(1),查询是O(n),如果维护另一个数组bi，表示a1到ai的和，那么修改是O(n),查询时O(1)。 一个程序的时间复杂度取决于其中最大的时间复杂度。 树状数组的目的就是平摊修改和查询的时间，使复杂度由O(n)降到O(lgn)。 树状数组是一种数据结构，这种结构能让我们的程序变得高效，数据结构大多数时数据结构大多数时候是为了优化算法而用的。候是为了优化算法而用的。4 树状数组对于原数组a维护另一个数组c，ci表示sum(aj),i-lowbit(i)+

3、1=j=i,其中lowbit(i)表示取出i二进制表示中最右边的1。 例如lowbit(6)=lowbit(110)2=(10)2=2 所以 c6=a5+a6; lowbit(4)=lowbit(100)2=(100)2=4 c4=a1+a2+a3+a4 lowbit5=lowbit(101) 2 =(1) 2=1; c5=a5 其比较简单的算法为 lowbit(i)=i & (-i) 或i & (i (i-1)56结论 1、节点i的父亲节点为i+lowbit(i) 2、节点i的最近不相交前驱为i-lowbit(i) 3、若需改变ai，则ci、ci+lowbit(i)、ci+l

4、owbit(i)+lowbit(i+lowbit(i)一直加到上限，就是需要改变的c数组中的元素。 4、若需查询si，则ci、ci-lowbit(i)、ci-lowbit(i)-lowbit(i-lowbit(i)就是需要累加的c数组中的元素。 5、以上的修改和查询都是log2(n)级别的。7Procedure add(k,delt);Begin while k=limit do begin Ck:=Ck+delta; k:=k+lowbit(k); End;End;由此我们可以得出修改与查询操作void add(k,delt) while(k0 do begin t:=t+ck; k:=k-

5、lowbit(k); end; getsum:=t;End;当要查询ai.j累加和时，可以先求出a1.j,a1.i-1，然后相减int getsum( int k) int t=0; while (k0) t+=ck; k- =lowbitk; return t;9 在实际应用中，通常不需要保存原数组a，只保存数组c即可。因此，树状数组几乎不需要附加空间。 通过上面的学习可以看出：树状数组所能支持的操作是修改点值、查询区间和。修改点值、查询区间和。10 与线段树和其他数据结构相比，树状数组代码简单，常数小，在其能解决范围内或经过转化使用树状数组，可以极大的降低编程复杂度，使代码清晰，简洁优 秀

6、 的 数 据 结 构 ！优 秀 的 数 据 结 构 ！11例题、Stars(ural 1028) 题目大意 平面中有N个点，对于 每个点(x,y)，要求输 出在其左下方（包括正 左正下）点的个数。 N=100000; x,y=maxlongint12 枚举？ 代码简单，时间复杂度达到O(n2) 有没有代码简单、时间复杂度低的方法？13 此题有效的算法很多，树状数组可以简洁快速的解决此问题。 如何构建树状数组？ 如何处理巨大的(x,y)？ 如何处理“左下方”？14 首先，离散化y坐标，然后按x坐标从小到大 排序，x相同则y坐标由小到大，从左到右扫描每个点，这样可以保证已经插入树状数组的点都在左侧

7、或正下侧。 我们只需寻找有 多少点位于当前点下 方，很容易想到树状 数组。处理完当前点 后，将其按y坐标插入 树状数组，即让ay加115 此题是树状数组的经典应用 首先离散化坐标使数据范围减小，为使用树状数组创造了条件 按横坐标排序，使得原题中“左下方”两个条件限制转化为“下方”这一单一限制 可以轻松运用树状数组解决16现在，我们将树状数组推广到二维 先看一道神奇的题目172、Superbrother打鼹鼠(vijos 1512) 题目大意 给定一个n*n的正方形区域，左上角为(0,0) ,右下角为(n-1,n-1)，初始所有整点权值为0。任意时刻有两种操作： 1、在一个整点处权值加K 2、询

8、问一个矩形内整点权值和 N0 do begin z:=y; while z0 do begin t:=t+cx,z; z:=z-lowbit(z); end; x:=x-lowbit(x); end; getsum:=t;End; 20 对于询问(x1,y1)-(x2,y2)， ans=getsum(x2,y2)-getsum(x2,y1-1)-getsum(x1-1,y2) +getsum(x1-1,x2-1);21树状数组下标必须从1开始Superbrother神牛22 到此，我们已经学习完树状数组的基本内容。 树状数组的应用非常广泛，变形极多，灵活性强，很多题目经过一系列转化后可以使用树

9、状数组解决。 下面，我将通过其他几个例题介绍如何通过有效的转化使用树状数组解题。233、Cows(pku 2481) 题目大意 有n头牛，每头牛喜欢吃si,ei这个区间的草。如果对于i、j两头牛，si=sj且ej=si且等号最多成立一个，那么i比j强。输出每头牛比多少头牛强。 N,s,e=10524 样例输入 样例输出 3 1 0 0 1 2 0 3 3 4 25 此题条件简单，但并不直观 将区间坐标化，我们发现，对于每头牛，要求的就是其左上方的牛的个数。 同stars，注意判断点重合的情况264、逆序对 题目大意 给定一个序列a1.an，对于任意i,j,如果iaj，我们说这是一个逆序对。 你

10、的任务是输出逆序对的个数 N=100000 ai=maxlongint27 此题直接枚举同样需要n2的时间 此题同样解法较多，可以使用分治法类似归并排序，也可以使用树状数组。 此题和stars同样有两个限制: “iaj” 应用同一思路，顺序扫描，将其转化为一个限制aiaj。28 首先对a数组离散化 按顺序扫描，只需找到有多少比ai大的数已经出现过。这可以用树状数组维护。 初始时，数组全为0。每次扫描到ai，用树状数组求出ai+1max中出现过多少个数，然后将ai插入树状数组。29 例如n=5,输入100 6 7 2 3 首先离散化，输入变为5 3 4 1 2 顺序扫描i123451000003

11、0 例如n=5,输入100 6 7 2 3 首先离散化，输入变为5 3 4 1 2 顺序扫描i1234520000131 例如n=5,输入100 6 7 2 3 首先离散化，输入变为5 3 4 1 2 顺序扫描i1234530010132 例如n=5,输入100 6 7 2 3 首先离散化，输入变为5 3 4 1 2 顺序扫描i1234540011133 例如n=5,输入100 6 7 2 3 首先离散化，输入变为5 3 4 1 2 顺序扫描i1234551011134小结 以上几道例题比较简单，属于树状数组的基础用法，主要起到数据结构的作用，用来对数据进行快速的存储和处理。 树状数组与其他数

12、据结构相比，最大的特点就是代码简单，常数小，从而得到广泛的应用。 树状数组的基本操作就是两个，修改某个元素的值，求区间累加和。35括号 括号表示法是运用树状数组解题的重要方法之一。 应用括号表示，可以将一部分修改区间、查询点值的题目转化为修改点值、查询区间，从而可以使用树状数组。365、Superbrother种树 实验中学东校坐落在济南市郭店镇。为了迎全运，树新风，需要在一条长为n的道路上种若干种树。道路表示为0,n，共n+1个点。由于经费紧张，教导处将这个重任交给了信息组头号神牛Superbrother，希望他合理分配树木，使道路更加漂亮。37 Superbrother经过研究，制定了一套

13、详细的计划。计划可以描述为若干个操作，每个操作在l,r中所有点种一棵颜色特殊的树。 教导处随时都会检查，方式为给定一个点，要求他回答这个点一共种过多少种不同的树。 输入第一行为n,m 以下m行，可能是一次种树，也可能是一次询问。38 此题与前面几题不同，要求修改一段区间的值，询问一个点的值。 使用线段树可以轻松处理。 有没有更简单、快速的方法？ 利用括号，转化为树状数组利用括号，转化为树状数组39 要将修改区间操作转化为修改点的操作，只有在区间端点做文章。 每次修改区间，便在区间两端加括号。这样，每次询问时只需要输出从0这个点中左括号数-右括号数。40 具体的，对于每个修改操作l,r，将树状数

14、组中cl+1,cr+1-1。对于询问操作t，输出getsum(t)。 时间复杂度O(mlgn)416、Matrix(pku 2155) 题目大意 给定一个n*n的01矩阵，初始全部为0。要求维护两个操作： 1、C x1 y1 x2 y2 ，子矩阵(x1,y1)(x2,y2)中数 值全部取反 2、Q x y ，询问点(x,y)的值42样例输入 样例输出 2 10 1 C 2 1 2 2 0 Q 2 2 0 C 2 1 2 1 1 Q 1 1 C 1 1 2 1 C 1 2 1 2 C 1 1 2 2 Q 1 1 C 1 1 2 1 Q 2 1 43 此题是区间求反问题，而树状数组所维护的是区间和

15、问题。 如何转化？ 注意到所求为一个点 的值，而点值只与 求反操作次数有关44 首先考虑一维情况 原问题变为：对于一个数列，每次对一段区间取反，询问一个点的值。 由于一个点的值只与取反次数有关，所以我们记录每个点的取反次数。 树状数组支持的操作是修改一个点的值，查询一段区间的和。而此题恰恰相反。 如何改变树状数组的意义？ 括号括号45 每次对一段区间(a,b)取反，可以看成加了一对括号。 每次询问只需求出从1到k中左括号-右括号,即为点k修改的次数 46 数组ci记录1i中左括号-右括号的值。 每次修改(a,b),ca加1，cb+1减1。 这样，每次询问求出ck，判断奇偶即可。 如何推广到二维

16、？47 查询操作不变，对于每次修改操作 (x1,y1)-(x2,y2)，我们仿照一维情形加“括号”。 具体的cx1,y1+1,cx2+1,y2+1+1cx1,y2+1-1,cx2+1,y1-1487、密码机 题目大意 有一个初始为空的序列。维护三种命令： 1、ADD把Number加到数列最后 2、REMOVE在数列中找到等于的数，删除 3、xor between and 对于数列中所有在Number1,Number2中的数异或并输出结果 加入的数不超过20000，询问次数=6000049 算法一：直接处理算法一：直接处理 对于Add操作，直接将Number添加到数组尾端。O(1) 对于Remo

17、ve操作，直接查询并删除。O(n) 对于Xor操作，枚举每一个元素。O(n) 时间复杂度O(T*n)50 小优化小优化 Xor操作即按位异或. 1 xor 1=0. 1 xor 0=1. 0 xor 0=1. 对于delete操作，我们其实可以将其视为Add操作。因为a xor a=0. a xor 0=a，所以delete(Number)将相当于add(Number) 这样Delete操作复杂度降到(1) 算法的瓶颈在于询问操作51 由于询问操作可能达到O(n)，所以如果要降低时间复杂度，就不能枚举全部符合条件的数然后异或，只能利用某些方法一起计算。 观察输入，我们发现加入的数不超过2000

18、0，如何利用这个条件？ 树状数组树状数组!52 算法二：树状数组算法二：树状数组 将Add操作和Delete操作看成Add，把树状数组操作中加法改成xor。可以证明，这种方法可以得到正确的结果。 对于询问l,r，因为a xor a=0,a xor 0=a，可以直接输出get(r) xor get(l-1) 每个操作复杂度均为logn，总时间复杂度为O(Tlogn)538、Jason911追MM Ssfz神牛颇多，但最会追MM的当属Jason911。这一天jason911发现n个MM，jason911非常高兴，很想让她们全当自己GF。但是她发现如果如果找太多GF会让她们很不满意，于是他决定只找5

19、个MM当GF。 MM们按顺序排成1n，各有一个魅力值。Jason911决定，他要使找到GF的魅力值严格递增，这样才能心情愉快。 他想知道一共有多少种选法54 例如有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个55 对于一般的LIS，可以使用动态规划，运用二分可以达到(nlogn)。 本题要求方案数，朴素的DP可以另维护一个数组gi,j表示表示以i为结尾、长度为j的上升子序列的种数。 能否仍用二分，同时求出方案数？5

20、6 考虑使用树状数组记录次数和长度 此题要求LIS长度为5，即可分为5个阶段。分别为15，各开一个树状数组，记录方案数。 具体的，扫描到每个MM时，首先将其加入到第一个树状数组，然后j从1循环到4，判断能够找到多少魅力值小于她的MM，并加入到下一个树状数组。57长度12345671+1234558长度12345671+11234559长度1234567111+12+234560长度12345671111+122+334561长度1234567111112233+24562长度123456711111+1223+4324563长度1234567111111223432+54564长度123456

21、711111122343254+2565长度1234567111111+12234+532542566长度1234567111111122345325+942567长度1234567111111122345325942+7568长度123456711111112234532594275+269长度1234567111111+112234+5532594275270长度123456711111111223455325+994275271长度1234567111111112234553259942+775272长度1234567111111112234553259942775+2273长度1234

22、5671111111122345532599427752274小结 利用括号的思想，树状数组可以在一定程度上解决修改区间、查询点值的功能。 对于一些状态阶段、要求统计方案数的题目，常使用多棵树状数组分阶段记录，并在阶段之间转移。759、Japan(pku 3067) 题目大意 给定一个二分图，左边M个点，右边N个点，从上倒下分别为1,2,3中间有一些边连接两端的点，任意三条边不共点。求出总交点个数 M,N=1000,k=10000076样例输入 3 4 4 (n,m,k) 1 4 2 3 3 2 3 1 77 如何运用点的有序性？ 相交的实质？78 (x1,y1),(x2,y2)两边相交的条件

23、: x1y2 应用同样的思路，转化 为一个条件！79 按左端点对边排序（如果相同则右端点小的在前）。扫描每一条边，这样保证了已经加入边的左端点在当前边上方。 这样只需查找有多少 条已经扫描过的边的 右端点在当前边下方。80 如图，当扫描到红色边时，我们需要查找的区域即为3,4，各有一条边形成相交 由此，问题变成了改变 点的值，询问一个区间 内点值和 树状数组！ 81树状数组求最值 问：树状数组能求最值么？ 前项的最值是可以求的。只要把求和改成就可以了。 但是求，之间的最值能求么？ 思考一下！ 好像无从下手。 我们先讨论先构造，只查询，不修改的那种模式。82修改值还是和求和一样的void Init(int n) for(int i=1;i=n;i+) for(int j=i;j=n;j+=Lowbit(j) cj=MAX(cj,numi); 这种方法在每次调用该函数前都必须对数组进行初始化， 这样对于数据范围比较大的时候不是很优美, 这样我们可以改为： void Init(i