重拾数据结构
要考蓝桥杯了，但是我现在好菜啊。。。
树状数组
原理
看懂这张图就行：
其中黑色的是原数据，红色的是树。不难发现树的节点数和原数据的数量一样，因此很省空间。其中8号节点包含所有子节点的信息，因此区间[1,8]对应8号节点，同理，区间[5,6]对应6号节点。
为了之后的操作，我们需要搞清楚两个关系：如何找到区间[1,n]所涉及的所有节点，如何找到一个节点的所有父节点。
lowbit函数
在探究上一个问题之前，先得了解这个lowbit函数。
lowbit(x)就代表x最右边的一堆0和一个1组合起来的二进制所代表的值。比如lowbit(4)=4,lowbit(7)=1
找到区间[1,n]所涉及的所有节点
比如要找区间[1,6]涉及的所有节点，由图可得那就是4，6（4对应1到4，6对应5到6）
观察其二进制：4(100)，6(110)。不难发现，6减去lowbit(6)就是4。
因此对于区间[1,n],不断让n减去lowbit(n)直到为0，这期间涉及的数就是区间1到n涉及的节点
从子节点找父节点
要找5这个点的父节点，那么就相当于要找6（110），8（1000）三个节点的值。不难发现，如果把5的父节点排成一排，也就是5，6，8，则相邻两项的差值正好等于前一项的lowbit值，也就是6=5+1，8=6+2
因此如果要找到x的父节点，我们就不断的让x加上lowbit(x)，直到x被加到n为止。这期间内被加到过的值就是x的父节点
比如3(101)这个节点的父节点，就是4(100)，8(1000)
操作
朴素的树状数组支持点更新和区间求和：
点更新
比如要更新5号点，根据上面的讨论，我们让5不断加上其lowbit值，也就是：
5+lowbit(5)=6,6+lowbit(6)=8,因此我们会更新5，6，8号点的值。
区间查询
比如要查询[1,5]，我们就不断让5减去lowbit，也就是5-lowbit(5)=4,4-lowbit(4)=0,因此我们需要查询4，5号点的数据并汇总
操作的时间复杂度
$O(logn)$，证明略
树状数组扩展版
使用树状数组实现区间修改和区间查询
设原数组为$data[i]$，定义差分数组$tree[i]=data[i]-data[i-1]$，则
1：有$data[i]=\sum_{j=1}^{i}tree[i]$，因此如果要求得原数组的第a个值，就可以转换为求差分数组的前a个值之和
2：$\sum_{i=1}^ndata[i]=\sum_{i=1}^n\sum_{j=1}^{i}tree[i]=tree[1]+(tree[1]+tree[2])+(tree[1]+tree[2]+tree[3])+…+(tree[1]+…+tree[n])=ntree[1]+(n-1)tree[2]+…+(n-a+1)tree[a]+…+tree[n]=\sum_{i=1}^{n}(n-i+1)tree[i]$，因此如果令$tree2[a]=(n-a+1)tree[a]$，要求得区间的和，就需要求$\sum_{i=1}^{n}tree2[i]$的值；要修改某一个节点的值，就需要同时修改$tree[i]$和$tree2[i]$的值，
3：如果需要区间修改，比如在区间上每一个数加上a，根据差分的定义，就应该在tree数组的区间左端点-1处加上a，右端点处减去a，这样就巧妙的将区间修改转化为了点修改
模版
#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)
#define ll long long
#define clean(arry,num) memset(arry,num,sizeof(arry))
#define anti_loop(i,start,end) for(register int i=start;i>=end;--i)
#define lowbit(x) ((x&(-x)))
const int maxn = 1000000+10;
ll tree[maxn],data[maxn],tree2[maxn];
ll n,m;
template<typename T>void read(T &x){
x=0;register char r=getchar();T neg=1;
while(r>'9'||r<'0'){if(r=='-')neg=-1;r=getchar();}
while(r>='0'&&r<='9'){x=(x<<1)+(x<<3)+r-'0';r=getchar();}
x*=neg;
}
inline void add(ll pos,ll data_){
ll x=pos;
while(pos<=n){
tree[pos]+=data_;
tree2[pos]+=(x-1)*data_;
pos+=lowbit(pos);
}
}
inline ll getsum(int pos){
ll res=0,x=pos;
while(pos>0){
res += x*tree[pos]-tree2[pos];
pos-=lowbit(pos);
}
return res;
}
inline void update(int l,int r,int data_){
add(l,data_);
add(r+1,-data_);
}
inline ll query(int l,int r){
return getsum(r)-getsum(l-1);
}
inline void buildtree(int i){
add(i,data[i]-data[i-1]);
}
int main(){
//freopen("datain.txt","r",stdin);
read(n);read(m);
loop(i,1,n){
read(data[i]);
buildtree(i);
}
int opt,x,y,k;
loop(i,1,m){
read(opt);
if(opt == 1){
read(x);read(y);read(k);
update(x,y,k);
}
else{
read(x);read(y);
printf("%lld\n",query(x,y));
}
}
return 0;
}线段树
区间加减的线段树的模版
#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(int i=start;i<=end;++i)
#define ll long long
const int maxn = 1e5+10;
ll data[maxn], lazy[maxn<<2], sum[maxn<<2];
void pushup(int rt){
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
return;
}
void pushdown(ll rt,ll len){
if(!lazy[rt])return;
lazy[rt<<1] += lazy[rt];
lazy[rt<<1|1] += lazy[rt];
sum[rt<<1] += lazy[rt]*(len-(len>>1));
sum[rt<<1|1] += lazy[rt]*(len>>1); //右子树的区间长度一定是区间长度的一半
lazy[rt] = 0;
}
void buildtree(ll l,ll r,ll rt){
lazy[rt] = 0;
if(l == r){
sum[rt] = data[l];
return;
}
ll m = (l+r)>>1;
buildtree(l,m,rt<<1);
buildtree(m+1,r,rt<<1|1);
pushup(rt);
}
void add(ll l,ll r,ll nl,ll nr,ll rt,ll num){
if(l<=nl&&nr<=r){
lazy[rt] += num;
sum[rt] += num*(nr-nl+1);
return;
}
pushdown(rt,nr-nl+1);
ll m = (nr+nl)>>1;
if(m>=l)add(l,r,nl,m,rt<<1,num);
if(m<r)add(l,r,m+1,nr,rt<<1|1,num);//由于这里是m+1，因此m<r不能够取等号
pushup(rt);
}
ll query(ll l,ll r,ll nl,ll nr,ll rt){
if(l<=nl&&nr<=r)
return sum[rt];
ll m = (nl+nr)>>1;
ll res = 0;
pushdown(rt,nr-nl+1);
if(m>=l)res += query(l,r,nl,m,rt<<1);
if(m<r)res += query(l,r,m+1,nr,rt<<1|1);
return res;
}
int main()
{
//freopen("datain.txt","r",stdin);
ll n,q;
scanf("%lld%lld",&n,&q);
loop(i,1,n)scanf("%lld",&data[i]);
buildtree(1,n,1);
loop(i,1,q)
{
int op;
scanf("%d",&op);
if(op==1)
{
ll l,r,x;
scanf("%lld%lld%lld",&l,&r,&x);
add(l,r,1,n,1,x);
}
else if(op==2)
{
ll a,b;scanf("%lld%lld",&a,&b);
printf("%lld\n",query(a,b,1,n,1));
}
}
return 0;
乘法线段树的模版
#include<bits/stdc++.h>
/*
review：关键是优先级，我是真的看不懂题解里面那个自定义优先级是个什么鬼
按照我的理解，优先级只能先乘后加
如：sigma{a[i]+k}=sigma{a[i]}+n*k
意思就是一个区间同时乘上一个数的时候，相当于把其原数列乘上一个数同时把懒标记乘上一个数然后加起来
所以在pushdown的时候，若涉及乘法标记应该将子区间的add标记乘上一个值然后再下传标记
这样的话就保证了优先级
———— 2019-07-23 19:07:38 Andrew82106
*/
using namespace std;
#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define anti_loop(i,start,end) for(register int i=start;i>=end;--i)
#define clean(arry,num) memset(arry,num,sizeof(arry))
#define ll long long
template<typename T>void read(T &x){
x=0;char r=getchar();T neg=1;
while(r>'9'||r<'0'){if(r=='-')neg=-1;r=getchar();}
while(r>='0'&&r<='9'){x=(x<<1)+(x<<3)+r-'0';r=getchar();}
x*=neg;
}
const int maxn=100000+10;
const int maxm=100000+10;
int n,m;
ll mod;
ll sum[maxn<<2];
ll lazyA[maxn<<2];
ll lazyM[maxn<<2];//long long
inline void pushup(int rt){
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
sum[rt]%=mod;
}
void buildtree(int l,int r,int rt){
lazyA[rt]=0;
lazyM[rt]=1;
if(l==r){
read(sum[rt]);
sum[rt]%=mod;
return;
}
int mid=(l+r)>>1;
buildtree(l,mid,rt<<1);
buildtree(mid+1,r,rt<<1|1);
pushup(rt);
}
inline void pushdown(int rt,int l,int r){
if(!lazyA[rt]&&lazyM[rt]==1)return;
int mid=(l+r)>>1;
sum[rt<<1]=(lazyM[rt]*sum[rt<<1])%mod;
sum[rt<<1|1]=(sum[rt<<1|1]*lazyM[rt])%mod;//写反了？？
sum[rt<<1]=((mid-l+1)*lazyA[rt]+sum[rt<<1])%mod;
sum[rt<<1|1]=((r-(mid+1)+1)*lazyA[rt]+sum[rt<<1|1])%mod;
lazyA[rt<<1|1]=(lazyA[rt]+lazyA[rt<<1|1]*lazyM[rt])%mod;
lazyA[rt<<1]=(lazyA[rt]+lazyA[rt<<1]*lazyM[rt])%mod;
lazyM[rt<<1]=(lazyM[rt]*lazyM[rt<<1])%mod;
lazyM[rt<<1|1]=(lazyM[rt]*lazyM[rt<<1|1])%mod;
lazyA[rt]=0;
lazyM[rt]=1;
}
void Add(int l,int r,int nl,int nr,int rt,ll w){
if(l<=nl&&nr<=r){
sum[rt]=(w*(nr-nl+1)+sum[rt])%mod;
lazyA[rt]=(w+lazyA[rt])%mod;
return;
}
pushdown(rt,nl,nr);
int mid=(nl+nr)>>1;
if(mid>=l)Add(l,r,nl,mid,rt<<1,w);
if(mid<r)Add(l,r,mid+1,nr,rt<<1|1,w);
pushup(rt);
}
void Mul(int l,int r,int nl,int nr,int rt,ll w){
if(l<=nl&&nr<=r){
sum[rt]=(w*sum[rt])%mod;
lazyA[rt]=(lazyA[rt]*w)%mod;
lazyM[rt]=w*lazyM[rt]%mod;
return;
}
pushdown(rt,nl,nr);
int mid=(nl+nr)>>1;
if(mid>=l)Mul(l,r,nl,mid,rt<<1,w);
if(mid<r)Mul(l,r,mid+1,nr,rt<<1|1,w);
pushup(rt);
}
ll Que(int l,int r,int nl,int nr,int rt){
if(l<=nl&&nr<=r){
return sum[rt];
}
pushdown(rt,nl,nr);
int mid=(nl+nr)>>1;
ll res=0;
if(mid>=l)
res+=Que(l,r,nl,mid,rt<<1);
if(mid<r)
res+=Que(l,r,mid+1,nr,rt<<1|1);
pushup(rt);
return res;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("datain.txt","r",stdin);
#endif
read(n),read(m),read(mod);
buildtree(1,n,1);
int op;
loop(i,1,m){
read(op);
if(op==1){
int x,y;
ll k;
read(x),read(y),read(k);
Mul(x,y,1,n,1,k);
}
else if(op==2){
int x,y;
ll k;
read(x),read(y),read(k);
Add(x,y,1,n,1,k);
}
else if(op==3){
int x,y;
read(x),read(y);
printf("%lld\n",(Que(x,y,1,n,1))%mod);
}
}
return 0;
}本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 AndrewLee！
