树状数组简介

Size: px

Start display at page:

Download "树状数组简介"

娣回
7 years ago
Views:

1 树状数组入门教程引言在解题过程中, 我们有时需要维护一个数组的前缀和 S[i]=A[]+A[2]+...+A[i] 但是不难发现, 如果我们修改了任意一个 A[i],S[i] S[i+]...S[n] 都会发生变化可以说, 每次修改 A[i] 后, 调整前缀和 S 在最坏情况下会需要 O(n) 的时间当 n 非常大时, 程序会运行得非常缓慢因此, 这里我们引入树状数组, 它的修改与求和都是 O(logn) 的, 效率非常高理论为了对树状数组有个形象的认识, 我们先看下面这张图如图所示, 红色矩形表示的数组 C 就是树状数组这里,C[i] 表示 A[i-2 k +] 到 A[i] 的和, 而 k 则是 i 在二进制时末尾 0 的个数, 或者说是 i 用 2 的幂方和表示时的最小指数当然, 利用位运算, 我们可以直接计算出 2 k =i and (i xor (i-)) 或 i and (-i) 同时, 我们也不难发现, 这个 k 就是该节点在树中的高度, 因而这个树的高度不会超过 logn 所以, 当我们修改 A[i] 的值时, 可以从 C[i] 往根节点一路上溯, 调整这条路上的所有 C 即可, 这个操作的复杂度在最坏情况下就是树的高度即 O(logn) 另外, 对于求数列的前 n 项和, 只需找到 n 以前的所有最大子树, 把其根节点的 C 加起来即可不难发现, 这些子树的数目是 n 在二进制时的个数, 或者说是把 n 展开成 2 的幂方和时的项数, 因此, 求和操作的复杂度也是 O(logn) 树状数组 C, 其中 C[i]=a[i-2 k +]+ +a[i](k 为 i 在二进制形式下末尾 0 的个数 ) 由 c 数组的定义可以得出 : c[]=a[] c[2]=a[]+a[2]=c[]+a[2] c[3]=a[3] c[4]=a[]+a[2]+a[3]+a[4]=c[2]+c[3]+a[4] c[5]=a[5] c[6]=a[5]+a[6]=c[5]+a[6]

有个形象的认识, 我们先看下面这张图如图所示, 红色矩形表示的数组 C 就是树状数组这里,C[i] 表示 A[i-2 k +] 到 A[i] 的和, 而 k 则是 i 在二进制时末尾 0 的个数, 或者说是 i 用 2 的幂方和表示时的最小指数当然, 利用位运算, 我

2 c[7]=a[7] c[8]= a[]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]+a[8]=c[4]+c[6]+c[7]+a[8] c[6]=a[]+a[2]+ +a[6]=c[8]+c[2]+c[4]+c[5]+a[6] c 数组的结构对应一棵树, 因此称之为树状数组对应如下图形 : 在最后, 我们将给出一些树状数组的实现代码, 希望读者能够仔细体会其中的细节. 求最小幂 2 k C++ 语言 : int Lowbit(int t) return t & ( t ^ ( t - ) ); //end Pascal 语言 : Function lowbit(x:longint):longint; var t:longint; t:=x and (x (xor(x-)); exit(t); // 相当于 lowbit:=t; 建立树状数组 c 更新元素值子序列求和, 都与 2 k 有关所以令 lowbit(i)=2 k ( 其中 k 为 i 在二进制下未尾 0 的个数 ) 其实 lowbit(i)=2 k =i and (i xor (i-)) 以 i=6 为例 (6)0=(00)2 Xor (6-)0=(5)0=(00)2 (00)2 And (6)0=(00)2 (000)2 2

求最小幂 2 k C++ 语言 : int Lowbit(int t) return t & ( t ^ ( t - ) ); //end Pascal 语言 : Function lowbit(x:longint):longint; var t:longint; t:=x and (x (xor(x-));

3 2. 对某个元素进行加法操作 : 将 a[p] 的值加上一个值 x(x 可正可负 ) C++ 语言 : int plus(int p, int x) while(p <= maxn) //maxn 为给定范围的上限 c[p] += x; p += Lowbit(p); Pascal 语言 : procedure plus(p,x:longint); while p<=maxn do //maxn 为给定范围的上限 c[p]:=c[p]+x; p:=p+lowbit(p) 譬如, 修改 9 这个值, 我们要修改 c[9] = c[00] c[9+2^0] = c[0] = c[00] c[0+2^] = c[2] = c[00] c[2+2^2] = c[6] = c[0000] 修改 2 这个值, 我们要修改 c[2] = c[00] c[2+2^2] = c[6] = c[0000] c[6+2^4] = c[32] = c[00000] 依此类推, 直到上限 3. 求前 p 项和 : 统计 a[]...a[p] 的和 C++ 语言 : int sum(int p) int sum = 0; while(p > 0) sum+ = c[p]; p- = Lowbit(p); return sum; Pascal 语言 : Function sum(p:longint):longint; var s:longint; s:=0; while p>0 do s:=s+c[p]; p:=p-lowbit(p); exit(s); // 相当于 sum:=s; 譬如, 求 a[]+a[2]+a[3]+ +a[2] 的和 c[2] = c[00] c[2-2^2] = c[8] = c[000] c[8-2^3] = c[0] 所以 a[]+a[2]+a[3]+ +a[2] 的和为 c[2]+c[8] 3

c[0000] 修改 2 这个值, 我们要修改 c[2] = c[00] c[2+2^2] = c[6] = c[0000] c[6+2^4] = c[32] = c[00000] 依此类推, 直到上限 3. 求前 p 项和 : 统计 a[].

4 4. 统计 a[x]..a[y] 的值调用以上的 sum 操作 :sum[y]-sum[x-] 一维的树状数组的每个操作的复杂度都是 O(logn) 的, 非常高效它可以扩充为 n 维, 这样每个操作的复杂度就变成了 O((logn)^n), 在 n 不大的时候可以接受扩充的方法就是将原来改变和查询的函数中的一个循环改成嵌套的 n 个循环在 n 维的 c 数组中操作要注意树状数组能处理的是下标为..n 的数组, 绝对不能出现下标为 0 的情况因为 lowbit(0)=0, 这样会陷入死循环实战运用例给定 n 个数列, 规定有两种操作, 一是修改某个元素, 二是求子数列 [a,b] 的连续和数列的元素个数最多 0 万个, 询问操作最多 0 万次输入格式第一行 2 个整数 n,m(n 表示输入 n 个数列,m 表示有 m 个操作 ) 第二行输入 n 个数列接下来 M 行, 每行有三个数 k,a,b(k=0 表示求子数列 [a,b] 的和,k= 表示第 a 个数列加 b 值 ) 输出格式输出若干行数字, 表示每次 K=0 时对应输出一个子数列 [a,b] 的连续和输入样例 0 5 // 输入 n 个数列, 有 m 个操作 // 输入 n 个数 5 // 第个数加上 // 求数列到数列 3 的连续和为 // 求数列 4 到数列 8 的连续和为 // 第 7 个数加上 // 求数列 4 到数列 8 的连续和为 35 输出样例参考程序 Program treearray; const maxn=000; var c:array[..maxn]of longint; n,i,m,x,y,st,a,b:longint; function lowbit(x:longint):longint; lowbit:=((x-)xor x)and x; 4

改变和查询的函数中的一个循环改成嵌套的 n 个循环在 n 维的 c 数组中操作要注意树状数组能处理的是下标为.

5 procedure plus(p,x:longint); while p<=n do inc(c[p],x); inc(p,lowbit(p)); function sum(p:longint):longint; var s:longint; s:=0; while p>0 do inc(s,c[p]); dec(p,lowbit(p)); exit(s); Begin readln(n,m); fillchar(c,sizeof(c),0); for i:= to n do read(y); plus(i,y); for i:= to m do readln(st,a,b); if st=0 then writeln(sum(b)-sum(a-)) else plus(a,b); End. 例 2 数星星 Stars(ural028) 问题描述天空中有一些星星, 这些星星都在不同的位置, 每个星星有个坐标如果一个星星的左下方 ( 包含正左和正下 ) 有 k 颗星星, 就说这颗星星是 k 级的 5

plus(i,y); for i:= to m do readln(st,a,b); if st=0 then writeln(sum(b)-sum(a-)) else plus(a,b); End.

6 比如, 在上面的例图中, 星星 5 是 3 级的 (,2,4 在它左下 ) 星星 2,4 是级的例图中有个 0 级,2 个级, 个 2 级, 个 3 级的星编程任务给定星星的位置, 输出各级星星的数目给定 n 个点, 定义每个点的等级是在该点左下方 ( 含相等 ) 的点的数目, 试统计每个等级有多少个点 (n<=5000,0<=x,y<=32000) 输入格式第行一个整数 N(<=N<=5000), 表示星星的数目接下来 N 行给出每颗星星的坐标, 两个整数 X,Y(0<=X,Y<=32000) 不会有星星重叠星星按 Y 坐标增序列出,Y 坐标相同的按 X 坐标增序列出输出格式 N 行, 每行一个整数, 分别是 0 级, 级,2 级 N- 级的星星的数目输入样例输出样例 2 0 算法分析相当经典的树状数组题目, 一开始分析题目是第一感觉是二维的树状数组, 不过数据范围显然不容许的对于每个星星按 y 坐标从小到大排序, 相同 y 坐标按 x 坐标从小到大排序 ( 题目中数据已经有序 ), 输入顺序已排好序, 那么只要依次统计星星 i 之前 x 坐标小于等于 i.x 的星星有多少, 即是星星 i 的级别 y 坐标没用, 显然是一维树状数组应用, 这样也就成了树状数组的模型, 编码很简单设数组 a[x] 初始为 0, 表示在 x 坐标处星星的个数, 则求和 a[0] ~ a[x] 则为该星星的等级, 逐个处理每个星星有一个地方尤其要注意, 树状数组是以号为起始的, 而且只能用号 x 可能为 0, 为 0 会时陷入死循环, 处理时要将所有的 x+ ( 当然加上其它的也无所谓, 只是上限范围需要变大 ), 还有就是 x 的范围不能事先确定, 在 plus 的时候我直接加到了 x 取值范围的最大值 6

同的按 X 坐标增序列出输出格式 N 行, 每行一个整数, 分别是 0 级, 级,2 级 N- 级的星星的数目输入样例 5 5 7 3 3 5 5 输出样例 2 0 算法分析相当经典的树状数组题目, 一开始分析题目是第一感觉是二维的树状数组, 不过数据范围显

7 例 3 校门外的树 (vijo448) 问题描述校门外有很多树, 有苹果树, 香蕉树, 有会扔石头的, 有可以吃掉补充体力的如今学校决定在某个时刻在某一段种上一种树, 保证任一时刻不会出现两段相同种类的树, 现有两个操作 : K=, 读入 l,r 表示在 l - r 之间种上的一种树 K=2, 读入 l,r 表示询问 l - r 之间能见到多少种树 (l,r>0, 道路总长和操作数 <=50000) 输入文件第一行 n,m 表示道路总长为 n, 共有 m 个操作接下来 m 行为 m 个操作输出文件对于每个 k=2 输出一个答案输入输出样例 tree.in 算法分析 tree.out 2 这题看起来和树状数组没什么关系, 不过我们通过一定的转化, 可以利用树状数组很好地解决这个问题我们不妨把所有线段的端点看成括号序列, 即把询问的区间 [lq,rq] 看成在横坐标 lq 处的一个 [ 和 rq 处的 ], 即把插入的线段 [li,ri] 看成在横坐标 li 处的一个 ( 和 ri 处的 ) 稍作分析, 我们不难发现, 最后的答案等于 ] 左边 ( 的个数减去 [ 左边 ) 的个数那么我们现在做的就是对某个点做修改, 对某个前缀求和我们就可以很容易想到树状数组的做法 :. 建立两个树状数 T 和 T2, 分别维护 ( 和 ) 2. 若 K=, 读入 li,ri,plust(li,),plust2(ri,) 3. 若 K=2, 读入 lq,rq,sumt(rq-)-sumt2(lq-) 小结经过前面概念和例题的讨论, 我们应该体会到了树状数组的特点 : 程序短速度快 ; 也明白到它最常用的功能 : 维护部分和在竞赛中, 如果我们采用树状数组处理, 既可以保证程序的效率, 也可以大幅度减小调试难度, 为选手省下大量的时间, 可以说是极其划算的总结树状数组是和线段树有异曲同工的数据结构, 其优点在于高效, 写起来很好写, 并且是在线的数据结构 2 但其只能处理一次修改某一个点上的数据, 并不能有效处理一次修改一个区间的数据 ( 每次只能修改某一节点的值而不能修改整个树可以理解为区间的值 ) 3 能用树状数组的题, 一定能用线段树做, 但能用线段树做的题, 不一定能用树状数组做 7

个答案输入输出样例 tree.in 5 4 3 2 2 5 2 4 2 3 5 算法分析 tree.

龚亚夫在重新思考基础教育英语教学的理念一文中援引的观点认为当跳出本族语主义的思维定式后需要重新思考许多相连带的问题比如许多发音的细微区别并不影响理解和

龚亚夫在重新思考基础教育英语教学的理念一文中援引的观点认为当跳出本族语主义的思维定式后需要重新思考许多相连带的问题比如许多发音的细微区别并不影响理解和语音语篇语感语域林大津毛浩然改革开放以来的英语热引发了大中小学英语教育整体规划问题在充分考虑地区学校和个体差异以及各家观点的基础上遵循实事求是逐级定位逐层分流因材施教的原则本研究所倡导的语音语篇语感语域