1 线段树,and树状数组 kennethsnow.

Presentation on theme: "1 线段树,and树状数组 kennethsnow."— Presentation transcript:

1 1 线段树,and树状数组 kennethsnow

2 Problems with Intervals
区间查询 询问某段区间的某些性质（极值，求和，etc） 区间更新 某些操作影响了某段区间（统一加一个值……） 三个问题 更新点，查询区间 更新区间，查询点 更新区间，查询区间

3 一个使用了两年的经典问题 一个长度为N的一维数组(a[1]~a[N]) 我们每次对该数组有一些操作： 1、修改数组中某个元素的值
2、询问数组中某段区间的最大值 【1,5,4,1,6】---(max(1,4)=?)---> 5 3、询问数组中某段区间的和 【1,5,4,1,6】---(sum(3,5)=?)---> 11

4 线段树 如果只有一次询问？ 线段树——在O(log2N)的时间内完成每次操作 O(Qlog2N) 枚举相应区间内的元素，输出答案 O(N)
更多的询问？ Q次询问，O(NQ) That's too SLOW! 线段树——在O(log2N)的时间内完成每次操作 O(Qlog2N) Less than 1 seconds when N=Q=100000

5 线段树——结构 如何建树？ 如何记录信息？ 线段树的本质是一棵二叉树，不同于其它二叉树，线段树的每一个节点记录的是一段区间的信息。
e.g. 对于长度为5的数组a[1]~a[5] [1,5] [1,3] [4,5] [1,2] [3,3] [4,4] [5,5] [1,1] [2,2] 对于任一非叶子节点，若该区间为[L,R],则 左儿子为[L,(L+R)/2] 右儿子为[(L+R)/2+1,R] 如何建树？ 如何记录信息？

6 数组[1,5,4,1,6] max=6 sum=17 [1,5] [1,3] [1,2] [3,3] [4,5] [5,5] [4,4]
[2,2] [1,1] max=5 sum=10 max=6 sum=7 max=5 sum=6 max=4 sum=4 max=1 sum=1 max=6 sum=6 max=1 sum=1 max=5 sum=5

7 线段树——更新，a[2]=3 max=6 sum=14 max=6 sum=17 [1,5] [1,3] [1,2] [3,3] [4,5]
[5,5] [4,4] [2,2] [1,1] max=4 sum=7 max=5 sum=10 max=6 sum=7 max=5 sum=6 max=3 sum=4 max=4 sum=4 max=1 sum=1 max=6 sum=6 max=1 sum=1 max=5 sum=5 max=3 sum=3

8 线段树——查询 sum(3,5)? ans=11 [1,5] [1,3] [1,2] [3,3] [4,5] [5,5] [4,4]
[2,2] [1,1] ans=4 ans=7 ans=4

9 线段树——实现 每一个节点记录的信息？ struct Tree { int left,right; //区间的端点
int max,sum; //视题目要求而定 }； 如何记录左儿子和右儿子？

10 线段树——实现（II） 一维数组即实现了线段树节点的保存 我们用一个数组a记录节点，且根节点的下标为1， 对于任一节点a[k]，
[1,5] [1,3] [1,2] [3,3] [4,5] [5,5] [4,4] [2,2] [1,1] 1 我们用一个数组a记录节点，且根节点的下标为1， 对于任一节点a[k]， 它的左儿子为a[2*k] 它的右儿子为a[2*k+1] 2 3 5 4 7 6 一维数组即实现了线段树节点的保存 9 8

11 线段树——代码实现(建树） 建立一棵线段树，并记录原数组信息 如果原数组从a[1]~a[n],调用build(1,1,n)即可
void build(int id,int l,int r) { tree[id].left=l; tree[id].right=r; if (l==r) { tree[id].sum=tree[id*2].sum+tree[id*2+1].sum; tree[id].max=max(tree[id*2].max,tree[id*2+1].max; } else int mid=(l+r)/2; build(id*2,l,mid); build(id*2+1,mid+1,r); 如果原数组从a[1]~a[n],调用build(1,1,n)即可

12 线段树——代码实现(更新） 更新某个点的数值，并维护相关点的信息 若更新a[k]的值为val，调用update(1,k,val)即可
void update(int id,int pos,int val) { if (tree[id].left==tree[id].right) { tree[id].sum=tree[id].max=val; } else int mid=(tree[id].left+tree[id].right)/2; if (pos<=mid) update(id*2,pos,val); else update(id*2+1,pos,val); tree[id].sum=tree[id*2].sum+tree[id*2+1].sum; tree[id].max=max(tree[id*2].max,tree[id*2+1].max) 若更新a[k]的值为val，调用update(1,k,val)即可

13 线段树——代码实现(查询） 查询某区间内元素的和或最大值(以总和为例） 调用query(1,l,r)即可查询[l,r]区间内元素的总和
void query(int id,int l,int r) { if (tree[id].left==l&&tree[id].right==r) return tree[id].sum; //询问总和 else { int mid=(tree[id].left+tree[id].right)/2; if (r<=mid) return query(id*2,l,r); else if (l>mid) return query(id*2+1,l,r) return query(id*2,l,mid)+query(id*2+1,mid+1,r); } 调用query(1,l,r)即可查询[l,r]区间内元素的总和

14 线段树——时间复杂度 更新操作：由于总是一条路径从根到某个叶子，而树的深度为log2N,因而为O(log2N)

15 线段树——空间复杂度 设长度为N的数组在线段树中有F(N)个节点 因而对于2n<=N<=2(n+1)，有
若N=2n, F(N)=2(n+1) 若N=2(n+1)，F(N)=2(n+2) 因而对于2n<=N<=2(n+1)，有 2(n+1)<=F(N)<=2(n+2) F(N)<=4*N

16 线段树——空间复杂度（II） 线段树空间应开为原数组长度的4倍
（图片转自 线段树空间应开为原数组长度的4倍

17 线段树——小结 1、线段树可以做很多很多与区间有关的事情…… 2、空间复杂度~O(N*4)，每次更新和查询操作的复杂度都是O(logN)。
3、在更新和查询区间[l,r]的时候，为了保证复杂度是严格的O(logN)必须在达到被[l,r]覆盖的区间的结点时就立即返回。而为了保证这样做的正确性，需要在这两个过程中做一些相关的“懒”操作。 “懒操作”在更新区间的有关问题上至关重要~

18 树状数组 一个一维数组tree[] 其中tree[i]表示 [i-(i&(-i))+1,i]这个区间内a数组元素的和
想求a[1]~a[15]的值？ 15=(1111)2 tree[15]=sum[15,15] tree[14]=sum[13,14] tree[12]=sum[9,12] tree[8]=sum[1,8] sum[1,15]=tree[8]+tree[12]+tree[14]+tree[15] 执行的次数和二进制中‘1’的位数有关

19 树状数组——操作 read(int pos) 求 sum[1,pos]的答案
update(int pos,int v) 把a[pos]加上v 更新点查询区间 下标必须从1开始~ 如果要查询sum[l,r]呢？ read(r)-read(l-1)

20 树状数组——代码实现 int read(int pos) { int ans=0; while (pos>0)
ans+=tree[pos]; pos-=pos&-pos; } return ans;

21 树状数组——代码实现 void update(int pos,int val) { int ans=0;
while (pos<=MAXN) //MAXN为总长度 tree[pos]+=val; pos+=pos&-pos; }

22 树状数组——代码实现 特殊应用：找整个数列的第K小数 int find_Kth(int k,int N) { int now=0;
for (int i=20;i>=0;i--) now|=(1<<i); if (now>N || tree[now]>=k) now^=(1<<i); else k-=tree[now]; } return now+1;

23 树状数组——总结 1、树状数组可以更新点查询区间，也可以更新区间查询点，但一般不能更新区间查询区间。
2、单操作时间复杂度O(log2N),空间复杂度O(N). 3、代码简洁。 思考:1、如何实现树状数组更新区间查询点？(例如给某个区间统一加一个数，询问某点当前值） 2、修改tree数组的定义，使其能够实现更新某个点的值，并询问[1,pos]中的最大值。

24 线段树和树状数组比较 1、线段树可以做到的，树状数组不一定能，树状数组可以做到的，线段树一定能。 2、树状数组的常数明显小于线段树
3、线段树的代码量高于树状数组，但能解决的问题类型也多了很多。

25 线段树和树状数组进阶 将在下周继续……

26 26 Thank You！ By kennethsnow