当前位置：首页 > news >正文

算法总结：数据结构——树状数组线段树

news 2026/8/14 2:25:46

直接上题吧：
已知一个数列{ a i } \{a_i\}{ai}，你需要进行下面两种操作：
1.将某区间每一个数/某一个数加上k kk。
2.求出某区间每一个数的和/某一个数的值。

首先，暴力前缀和肯定是不行的，因为它无法快速完成区间的修改(不然还用啥树状数组/线段树)，
那么，直接开始：

树状数组

思想

如图，a aa数组是输入的数列，c cc数组存的是管辖范围内(管辖范围如图)的前缀和。

~~不难发现，~~c [ x ] c[x]c[x]的管辖范围是从x往前的l o w b i t ( x ) lowbit(x)lowbit(x)个数。
(l o w b i t lowbitlowbit表示一个数二进制的最低一位1，如l o w b i t ( 5 ) = 1 ， l o w b i t ( 12 ) = 4 lowbit(5)=1，lowbit(12)=4lowbit(5)=1，lowbit(12)=4)

另：如何求lowbit

直接用x&(-x)即可。
就这么粗暴的O ( 1 ) O(1)O(1)(^▽ ^ )_{原理嘛，大概就是神奇的补码嗯对}

修改(点修)

在树状数组内，如果要修改某个数的值，只需要把所有管辖它的c cc修改掉即可。
For example，如果要修改a [ 5 ] a[5]a[5]的值，那么只需修改c [ 5 ] ， c [ 6 ] ， c [ 8 ] ， c [ 16 ] 的 c[5]，c[6]，c[8]，c[16]的c[5]，c[6]，c[8]，c[16]的值即可。
那么如何找到下一个管辖区间呢？
还是l o w b i t lowbitlowbit，只需要用x xx加上l o w b i t ( x ) lowbit(x)lowbit(x)，就能找到下一个区间_{嗯，就是这么神奇}
如此，修改的时间复杂度便降到了O ( l o g n ) O(log\ n)O(logn)以下。

查询(区查)

同样，查询时，也只要顺着找上一个管辖区间一直加，就能得到[ 1 , x ] [1,x][1,x]区间的前缀和。
要找到上一个区间，也只需要用x xx减去l o w b i t ( x ) lowbit(x)lowbit(x)。
最后，求[ x , y ] [x,y][x,y]的区间和，再用[ 1 , y ] [1,y][1,y]的区间和减去[ 1 , x − 1 ] [1,x-1][1,x−1]的区间和即可。
时间复杂度同样小于O ( l o g n ) O(log\ n)O(logn)。

代码(P3374点修区查)

#include<bits/stdc++.h>usingnamespacestd;#defineN500001intc[N],n,m;intlowbit(intx){returnx&(-x);}voidadd(intx,intk){while(x<=n){c[x]+=k;x+=lowbit(x);}}intsearch(intx){ints=0;while(x){s+=c[x];x-=lowbit(x);}returns;}intmain(){cin>>n>>m;for(inti=1;i<=n;i++){inta;cin>>a;add(i,a);}while(m--){intop,x,y;cin>>op>>x>>y;if(op==1)add(x,y);elsecout<<search(y)-search(x-1)<<endl;}return0;}

(叠甲：函数名称不严谨，仅供图一乐)

进阶版(P3368区修点查)

区修，就肯定不能像刚才一样挨个改了，这时候就需要点儿更快的方法——差分。
_{本人自己是肯定想不出来的，因为根本就没学过差分现学的哈哈哈o-o}
用差分的思想，可以知道，修改[ x , y ] [x,y][x,y]区间的值，可以在x xx处加k kk，在y + 1 y+1y+1处减k kk。
询问某个数的值，也只需要将原数加上差分数组前缀和。
然后，把以上东西套个树状数组，遂成。

代码

#include<bits/stdc++.h>usingnamespacestd;#defineN500001#definelllonglongll n,m,a[N],c[N];lllowbit(ll x){returnx&(-x);}voidadd(ll x,ll k){while(x<=n){c[x]+=k;x+=lowbit(x);}}llsearch(ll x){ll s=0;while(x){s+=c[x];x-=lowbit(x);}returns+a[x];}intmain(){cin>>n>>m;for(inti=1;i<=n;i++)cin>>a[i];ll op,x,y,k;for(inti=1;i<=n;i++){add(i,a[i]-a[i-1]);}//差分树状数组初始化while(m--){cin>>op;if(op==1){cin>>x>>y>>k;add(x,k);add(y+1,-k);}else{cin>>x;cout<<search(x)<<endl;}}return0;}

线段树

想完成区修区查，线段树是更优解。

#include<bits/stdc++.h>usingnamespacestd;#defineN400001//极品4倍空间#definelllonglongll n,m,tree[N],lazy[N],a[N];voidbuild(ll o,ll l,ll r){if(l==r){tree[o]=a[l];return;}ll mid=(l+r)/2;build(o*2,l,mid);build(o*2+1,mid+1,r);tree[o]=tree[o*2]+tree[o*2+1];}//建树，防止被CCF老年机卡常voidpushdown(ll o,ll l,ll r){ll mid=(l+r)/2;if(lazy[o]){tree[o*2]+=(mid-l+1)*lazy[o];tree[o*2+1]+=(r-mid)*lazy[o];lazy[o*2]+=lazy[o];lazy[o*2+1]+=lazy[o];lazy[o]=0;}}//下传懒标记voidupdate(ll o,ll l,ll r,ll x,ll y,ll k){//结点编号，管辖左端点，管辖右端点，修改左端点，修改右端点，要修改的值if(x<=l&&r<=y){tree[o]+=(r-l+1)*k;lazy[o]+=k;return;}ll mid=(l+r)/2;pushdown(o,l,r);if(x<=mid)update(o*2,l,mid,x,y,k);if(y>mid)update(o*2+1,mid+1,r,x,y,k);tree[o]=tree[o*2]+tree[o*2+1];}//修改llquery(ll o,ll l,ll r,ll x,ll y){//结点编号，管辖左端点，管辖右端点，查询左端点，查询右端点if(x<=l&&r<=y)returntree[o];ll mid=(l+r)/2,sum=0;pushdown(o,l,r);if(x<=mid)sum+=query(o*2,l,mid,x,y);if(y>mid)sum+=query(o*2+1,mid+1,r,x,y);returnsum;}//查询intmain(){cin>>n>>m;for(inti=1;i<=n;i++)cin>>a[i];build(1,1,n);ll op,x,y,k;while(m--){cin>>op;if(op==1){cin>>x>>y>>k;update(1,1,n,x,y,k);}else{cin>>x>>y;cout<<query(1,1,n,x,y)<<endl;}}return0;}