前言
刚开始刷树状数组的时候只会模板，后面的题压根不会，于是就用别的算法水了几道。
后来板刷一本通的时候，感觉要不整个活就太亏了，于是有了这篇文章
「一本通 4.1 例 1」数列操作
算法：分块
树状数组板子题，用分块过了。
代码
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int N=1e5+10;
int a[N],pos[N],L[N],R[N],add[N],sum[N];
int n,t,m;
inline void init(){
t=sqrt(n);
for(int i=1;i<=t;i++) L[i]=(i-1)*t+1,R[i]=i*t;
if(R[t]<n) t++,L[t]=R[t-1]+1,R[t]=n;
for(int i=1;i<=t;i++){
sum[i]=0,add[i]=0;
for(int j=L[i];j<=R[i];j++) pos[j]=i,sum[i]+=a[j];
}
}
inline void change(int x,int k){
a[x]+=k,sum[pos[x]]+=k;
}
inline int query(int l,int r){
int p=pos[l],q=pos[r],ans=0;
if(p==q){
for(int i=l;i<=r;i++) ans+=a[i]+add[p];
}
else{
for(int i=p+1;i<=q-1;i++) ans+=sum[i];
for(int i=l;i<=R[p];i++) ans+=a[i]+add[pos[i]];
for(int i=L[q];i<=r;i++) ans+=a[i]+add[pos[i]];
}
return ans;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) cin>>a[i];
init();
while(m--){
int k,a,b;
scanf("%d%d%d",&k,&a,&b);
if(!k) printf("%d\n",query(a,b));
else change(a,b);
}
}
「一本通 4.1 例 2」数星星 Stars
算法：动态开点权值线段树
正解应该是权值树状数组，但我用了权值线段树，但空间不够，于是动态开点。
代码
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int N=6e4+10;
struct node{
long long num;
int ls,rs;
}tr[90005];
int tot=0;
inline void pushup(int x){
tr[x].num=tr[tr[x].ls].num+tr[tr[x].rs].num;
}
void insert(int &x,int l,int r,int k){
if(!x) x=++tot;
if(l==r){
tr[x].num++;
return;
}
int mid=(l+r)/2;
if(k<=mid) insert(tr[x].ls,l,mid,k);
else insert(tr[x].rs,mid+1,r,k);
pushup(x);
}
int query(int x,int l,int r,int ql,int qr){
if(!x) return 0;
if(l>=ql&&r<=qr) return tr[x].num;
int mid=(l+r)/2,sum=0;
if(ql<=mid) sum+=query(tr[x].ls,l,mid,ql,qr);
if(qr>mid) sum+=query(tr[x].rs,mid+1,r,ql,qr);
return sum;
}
int n,root;
int main(){
scanf("%d",&n);
while(n--){
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",query(root,0,N,0,x));
insert(root,0,N,x);
}
}
「一本通 4.1 练习 1」清点人数
算法：线段树
可以说是线段树板子题吧，自然是要用线段树的捏
代码
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int tr[N*4];
inline void pushup(int x){
tr[x]=tr[x*2]+tr[x*2+1];
}
void insert(int x,int l,int r,int k,int p){
if(l==r){
tr[x]+=p;
return;
}
int mid=(l+r)/2;
if(k<=mid) insert(x*2,l,mid,k,p);
else insert(x*2+1,mid+1,r,k,p);
pushup(x);
}
int query(int x,int l,int r,int ql,int qr){
if(l>=ql&&r<=qr) return tr[x];
int mid=(l+r)/2,sum=0;
if(ql<=mid) sum=query(x*2,l,mid,ql,qr);
if(qr>mid) sum+=query(x*2+1,mid+1,r,ql,qr);
return sum;
}
int n,k;
int main(){
scanf("%d%d",&n,&k);
while(k--){
char opt[2];
int m,p;
scanf("%s",opt);
if(opt[0]=='A'){
scanf("%d",&m);
printf("%d\n",query(1,1,n,1,m));
}
else if(opt[0]=='B'){
scanf("%d%d",&m,&p);
insert(1,1,n,m,p);
}
else{
scanf("%d%d",&m,&p);
insert(1,1,n,m,-p);
}
}
}
「一本通 4.1 练习 2」简单题
算法：线段树
区间取反，自然是要用可爱的线段树啦，维护个懒标记即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,tr[N*4],add[N*4];
inline void pushdown(int x){
if(add[x]){
add[x]=0;
add[x*2]^=1,add[x*2+1]^=1;
}
}
void update(int x,int l,int r,int ql,int qr){
if(l>=ql&&r<=qr){
add[x]^=1;
return;
}
pushdown(x);
int mid=(l+r)/2;
if(ql<=mid) update(x*2,l,mid,ql,qr);
if(qr>mid) update(x*2+1,mid+1,r,ql,qr);
}
int query(int x,int l,int r,int k){
if(l==r) return add[x];
pushdown(x);
int mid=(l+r)/2;
if(k<=mid) return query(x*2,l,mid,k);
return query(x*2+1,mid+1,r,k);
}
int main(){
scanf("%d%d",&n,&m);
while(m--){
int opt,l,r;
scanf("%d%d",&opt,&l);
if(opt==1){
scanf("%d",&r);
update(1,1,n,l,r);
}
else printf("%d\n",query(1,1,n,l));
}
}
「一本通 4.1 练习 3」打鼹鼠
算法：线段树+暴力+剪枝
本来想写二逼线段树的，但是xyz太懒了，不想写那么高难度的算法，于是她想暴力。
她写了个一维暴力，二维线段树的O(n2logn)暴力算法，果然挂了（73）
然后聪明的xyz就加了个剪枝（若一行里个数为0直接返回），就过了！！！
代码
#include <bits/stdc++.h>
using namespace std;
const int N=2100;
int tot=0,root[N],ls[N*N],rs[N*N],tr[N*N];
inline void pushup(int x){
tr[x]=tr[ls[x]]+tr[rs[x]];
}
void build(int &x,int l,int r){
x=++tot;
if(l==r) return;
int mid=(l+r)/2;
build(ls[x],l,mid),build(rs[x],mid+1,r);
pushup(x);
}
void add(int x,int l,int r,int k,int p){
tr[x]+=p;
if(l==r) return;
int mid=(l+r)/2;
if(k<=mid) add(ls[x],l,mid,k,p);
else add(rs[x],mid+1,r,k,p);
}
int query(int x,int l,int r,int ql,int qr){
if(!tr[x]) return 0;
if(ql<=l&&r<=qr) return tr[x];
int mid=(l+r)/2,sum=0;
if(ql<=mid) sum=query(ls[x],l,mid,ql,qr);
if(qr>mid) sum+=query(rs[x],mid+1,r,ql,qr);
return sum;
}
int n,m;
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++) build(root[i],0,n-1);
while(cin>>m&&m!=3){
if(m==1){
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
add(root[x],0,n-1,y,k);
}
else{
int x,y,x2,y2,sum=0;
scanf("%d%d%d%d",&x,&y,&x2,&y2);
for(int i=x;i<=x2;i++) sum+=query(root[i],0,n-1,y,y2);
printf("%d\n",sum);
}
}
}
后记
本文是xyz的整活，如果你真的想学树状数组，千万不要像她这么干
