直接上题吧已知一个数列{ 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)1lowbit(12)4lowbit(5)1lowbit(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点修区查)#includebits/stdc.husingnamespacestd;#defineN500001intc[N],n,m;intlowbit(intx){returnx(-x);}voidadd(intx,intk){while(xn){c[x]k;xlowbit(x);}}intsearch(intx){ints0;while(x){sc[x];x-lowbit(x);}returns;}intmain(){cinnm;for(inti1;in;i){inta;cina;add(i,a);}while(m--){intop,x,y;cinopxy;if(op1)add(x,y);elsecoutsearch(y)-search(x-1)endl;}return0;}(叠甲函数名称不严谨仅供图一乐)进阶版(P3368区修点查)区修就肯定不能像刚才一样挨个改了这时候就需要点儿更快的方法——差分。本人自己是肯定想不出来的因为根本就没学过差分现学的哈哈哈o-o用差分的思想可以知道修改[ x , y ] [x,y][x,y]区间的值可以在x xx处加k kk在y 1 y1y1处减k kk。询问某个数的值也只需要将原数加上差分数组前缀和。然后把以上东西套个树状数组遂成。代码#includebits/stdc.husingnamespacestd;#defineN500001#definelllonglongll n,m,a[N],c[N];lllowbit(ll x){returnx(-x);}voidadd(ll x,ll k){while(xn){c[x]k;xlowbit(x);}}llsearch(ll x){ll s0;while(x){sc[x];x-lowbit(x);}returnsa[x];}intmain(){cinnm;for(inti1;in;i)cina[i];ll op,x,y,k;for(inti1;in;i){add(i,a[i]-a[i-1]);}//差分树状数组初始化while(m--){cinop;if(op1){cinxyk;add(x,k);add(y1,-k);}else{cinx;coutsearch(x)endl;}}return0;}线段树想完成区修区查线段树是更优解。思想建一棵二叉搜索树(英文名曰B i n a r y S e a r c h T r e e , B S T Binary\ Search\ Tree,BSTBinarySearchTree,BST)每个结点管辖一个区间(用t r e e [ o ] tree[o]tree[o]来表示结点o oo管辖区间数的总和)。根据BST的性质结点o oo的左儿子编号为2 o 2o2o右儿子的编号为2 o 1 2o12o1。如果o oo管辖的区间为[ l , r ] [l,r][l,r]那么左儿子管辖的区间为[ l , m i d ] ( m i d l r 2 ) [l,mid](mid\frac{lr}{2})[l,mid](mid2lr​)右儿子管辖的区间为[ m i d 1 , r ] [mid1,r][mid1,r]。查询查询还是蛮简单的(相对于修改)。对于查询区间[ x , y ] [x,y][x,y]如果结点o oo所管辖的区间[ l , r ] [l,r][l,r]非严格包含于区间[ x , y ] [x,y][x,y](即x ⩽ l x\leqslant lx⩽l且r ⩽ y r\leqslant yr⩽y)那么在答案中直接加上t r e e [ o ] tree[o]tree[o]即可。如果两区间交叉那么要往下找并重复以上操作直到完全求出答案。时间复杂度O ( l o g n ) O(log\ n)O(logn)。修改有亿点复杂……key懒标记顾名思义如果在修改时把数据一个一个往下传会特别慢所以就要用更“懒”的办法修改数据。我们不妨把要修改的k kk先暂存在l a z y lazylazy数组中(多好听的名字)等到需要时再下传。要在[ x , y ] [x,y][x,y]区间内给每个数加上k kk对于结点o oo如果其所管辖的区间[ l , r ] [l,r][l,r]非严格包含于区间[ x , y ] [x,y][x,y]那么直接修改t r e e [ o ] tree[o]tree[o](加上k × ( r − l 1 ) k×(r-l1)k×(r−l1)相当于直接修改每个数)同时给o oo做上懒标记也就是给l a z y [ o ] lazy[o]lazy[o]加上k kk查询时再按需要下传。如果两区间交叉那么就要将懒标记下传给自己的左右儿子如此循环直到整个区间都被修改完毕。时间复杂度O ( l o g n ) O(log\ n)O(logn)。代码(P3372区修区查)线段树千好万好但是代码量有亿点多(光是上边这么多就把我写力竭了)代码细节有亿点繁琐……从开空间开始线段树就在做局用线段树必须开4倍空间证明我也不会开就完了然后后面的建树、传懒标记、修改、查询四大函数一写一个不吱声……算了直接欣赏一下吧(写完真力竭了)#includebits/stdc.husingnamespacestd;#defineN400001//极品4倍空间#definelllonglongll n,m,tree[N],lazy[N],a[N];voidbuild(ll o,ll l,ll r){if(lr){tree[o]a[l];return;}ll mid(lr)/2;build(o*2,l,mid);build(o*21,mid1,r);tree[o]tree[o*2]tree[o*21];}//建树防止被CCF老年机卡常voidpushdown(ll o,ll l,ll r){ll mid(lr)/2;if(lazy[o]){tree[o*2](mid-l1)*lazy[o];tree[o*21](r-mid)*lazy[o];lazy[o*2]lazy[o];lazy[o*21]lazy[o];lazy[o]0;}}//下传懒标记voidupdate(ll o,ll l,ll r,ll x,ll y,ll k){//结点编号管辖左端点管辖右端点修改左端点修改右端点要修改的值if(xlry){tree[o](r-l1)*k;lazy[o]k;return;}ll mid(lr)/2;pushdown(o,l,r);if(xmid)update(o*2,l,mid,x,y,k);if(ymid)update(o*21,mid1,r,x,y,k);tree[o]tree[o*2]tree[o*21];}//修改llquery(ll o,ll l,ll r,ll x,ll y){//结点编号管辖左端点管辖右端点查询左端点查询右端点if(xlry)returntree[o];ll mid(lr)/2,sum0;pushdown(o,l,r);if(xmid)sumquery(o*2,l,mid,x,y);if(ymid)sumquery(o*21,mid1,r,x,y);returnsum;}//查询intmain(){cinnm;for(inti1;in;i)cina[i];build(1,1,n);ll op,x,y,k;while(m--){cinop;if(op1){cinxyk;update(1,1,n,x,y,k);}else{cinxy;coutquery(1,1,n,x,y)endl;}}return0;}本人写代码已经很不爱换行了基本上能一行塞下的东西就不会换行留空行的行为更是不存在线段树的代码也就只写了《63行》要是再空几行代码量《也就70行》要是实际做题代码量《也就100来行》要是写个不太正常的代码……《也就200行》By the way谁懂一个被橙题卡住的蒟蒻看到连模版都冒绿光的满屏绿题的救赎感o(╥﹏╥)o