【转载】【技术】你说你用什么做出来的？！
2026-02-06 12:06:53
发布于：浙江
25阅读
0回复
0点赞
众所周知，树状数组是一种很美味的东西，其代码如下：
#include<bits/stdc++.h>
using namespace std;
int lb(int x){
return x&-x;
}
long long ta[1000010],a[1000010],n,q;
void ce(int x,int v){
while (x<=n){
ta[x]+=v;
x+=lb(x);
}
}
long long qr(int x){
long long r=0;
while (x){
r+=ta[x];
x-=lb(x);
}
return r;
}
int main()
{
cin>>n>>q;
for (int i=1;i<=n;++i){
cin>>a[i];
ce(i,a[i]);
}
while (q--){
int op,l,r,k;
cin>>op;
if (op==1){
cin>>l>>k;
ce(l,k);
}else{
cin>>l>>r;
cout<<qr(r)-qr(l-1)<<endl;
}
}
return 0;
}
我们知道它支持单点修改，前缀查询。懒标记搞不了，逆运算搞不了，复杂操作搞不了……
Q:所以树状数组有啥用？
A:逆天码量，和暴力接近，而很多题都只需要单点修改和前缀查询。
基础用法
单点修改，单点求值，区间修改，区间查询等基础内容不再叙述
有帮助，赞一个