线段树真是太强啦!
线段树不同与树状数组,他支持单点查询,单点修改,区间修改,区间查询,需要 \(4\) 个函数进行,分别为 \(build,updata,query,lazy\) 组成,即搭建,更新,查询,懒惰数组。
定义一个数组,我们称为 \(tree\) 对于 \(tree_i\) 我们同样保留 \(4\) 个元素,\(l,r,num,lazy\) 分别记录左端点,右端点,端点和,和懒惰值。然后开始搭建树,我们搭建一颗完全二叉树第一层的元素记录 \(1\) 到 \(n\) 的元素和,第二层左儿子记录 \(1\) 到 \(n/2\) ,右儿子记录 \(n/2+1\) 到 \(n\) , 以此类推。父节点的值为子节点的值之和。
性质:对于任意一个父节点,令他的编号为 \(x\) ,则他的左儿子编号为 \(x \times 2\) ,右儿子为 \(x \times 2 +1\)。
Code:
void build(int l,int r,int p){ tree[p].l=l; tree[p].r=r; if(l==r){ tree[p].num=a[l]; return; } build(l,(l+r)/2,p*2); build((l+r)/2+1,r,p*2+1); tree[p].num=tree[p*2].num+tree[p*2+1].num; return; }
先找到父亲所在的 \(tree\) 数组,打上懒惰数组(等下会讲),然后返回,否则,就继续找,一直到 \(l,r\) 的值都算出来。如果找的途中懒惰数组需要用到,就通过 \(lazy\) 操作让懒惰数组向儿子赋值。
Code:
void updata(int l,int r,int k,int number){ int left=tree[number].l,right=tree[number].r; if(left>r||right<l) return; if(l<=left&&right<=r){ tree[number].num+=k*(right-left+1); tree[number].lazy+=k; return; } if(tree[number].lazy>0) lazy(number); updata(l,r,k,number*2); updata(l,r,k,number*2+1); tree[number].num=tree[number*2].num+tree[number*2+1].num; return; }
为什么线段树能支持区间修改?原因就是懒惰数组,对于每一次修改,如果我们只需要要求一个大区间的值,那么我们只需要修改大区间的值,根本不需要修改小区间的值。如果我们后面需要修改小区间的,我们在修改小区间即可。这样,就节省了时间。
Code:
void lazy(int number){ //number 为节点编号 tree[number*2].num+=(tree[number*2].r-tree[number*2].l+1)*tree[number].lazy; tree[number*2+1].num+=(tree[number*2+1].r-tree[number*2+1].l+1)*tree[number].lazy; tree[number*2].lazy+=tree[number].lazy; tree[number*2+1].lazy+=tree[number].lazy; tree[number].lazy=0; return; }
这个我就不多赘述,直行看代码即可理解。
Code:
long long query(int l,int r,int number){ int left=tree[number].l,right=tree[number].r; if(left>r||right<l) return 0; if(l<=left&&right<=r){ return tree[number].num; } if(tree[number].lazy!=0) lazy(number); return query(l,r,number*2)+query(l,r,number*2+1); } }
一个总代码,为洛谷 P3372 Ac代码
#include<iostream> using namespace std; long long n,m,a[100005],x,y,z,k; struct node{ int l,r; long long num,lazy; }tree[4*100005]; void build(int l,int r,int p){ tree[p].l=l; tree[p].r=r; if(l==r){ tree[p].num=a[l]; return; } build(l,(l+r)/2,p*2); build((l+r)/2+1,r,p*2+1); tree[p].num=tree[p*2].num+tree[p*2+1].num; return; } void updata(int number){ tree[number*2].num+=(tree[number*2].r-tree[number*2].l+1)*tree[number].lazy; tree[number*2+1].num+=(tree[number*2+1].r-tree[number*2+1].l+1)*tree[number].lazy; tree[number*2].lazy+=tree[number].lazy; tree[number*2+1].lazy+=tree[number].lazy; tree[number].lazy=0; return; } void add(int l,int r,int k,int number){ int left=tree[number].l,right=tree[number].r; if(left>r||right<l) return; if(l<=left&&right<=r){ tree[number].num+=k*(right-left+1); tree[number].lazy+=k; return; } if(tree[number].lazy>0) updata(number); add(l,r,k,number*2); add(l,r,k,number*2+1); tree[number].num=tree[number*2].num+tree[number*2+1].num; return; } long long find(int l,int r,int number){ int left=tree[number].l,right=tree[number].r; if(left>r||right<l) return 0; if(l<=left&&right<=r){ return tree[number].num; } if(tree[number].lazy!=0) updata(number); return find(l,r,number*2)+find(l,r,number*2+1); } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } build(1,n,1); while(m--){ cin>>z; if(z==1) { cin>>x>>y>>k; add(x,y,k,1); }else { cin>>x>>y; long long sum=find(x,y,1); cout<<sum<<endl; } } return 0; }