题解：P3368 【模板】树状数组 2
IGA_Indigo
·
2025-04-07 21:42:11
·
题解
题目大意
树状数组模板题，要求在 1 \leq N, M\le 500000 的数据下实现区间加和单点查询。
大体思路
树状数组教学
树状数组其实是一个相当优美的算法了，其中使用的 lowbit 十分精妙。
//lowbit
int lowbit(int k){
return k&(-k);
}lowbit 的含义是什么呢？为什么 lowbit 能够这么快速的实现此类问题呢，我们先来看一张图（from OI-Wiki）。
这里运用了负数的存储特性，负数是用补码存储的，例如当 i 为奇数时，最后一位是 1 取反加一并没有进位，所以 lowbit 结果正好是 1 ，相同的我们可以推得，如果 i 为偶数，结果是 k\le i 最大的 2^k ，其中 k 为整数，有兴趣的小伙伴可以自己分类讨论推导一下，探讨偶数时可以分成 2^k 和 y\times 2^k 两种，然后就可以发现后者其实是用一个奇数左移 k 位来表示的（说多了）。
举个例子，$lowbit(1)=1$，正好 $C[1]$ 就是存 $A[1-1+1](A[1])$ ，$lowbit(2)=2$，正好 $C[2]$ 就是存 $A[2-2+1]+A[2-2+2](A[1]+A[2])$，$lowbit(3)=1$，$C[3]$ 就是存 $A[3-1+1](A[3])$。
也就是说，树状数组通过使用 lowbit 来存储一部分节点，能用很少的空间实现一部分线段树的功能，而且常数较小。
### 回到本题
本题中，由于一开始的数是固定的，所以我们只需要用树状数组来记录变更的值。
区间修改单点查询，我们使用差分数组思想。
- 区间加
我们要进行的区间加操作，需要从 $x$ 扫到 $n$，对差分数组进行操作。
```cpp
void add(int x,int k){
while(x<=n){
t[x]+=k;
x+=lowbit(x);
}
}
```
毕竟是差分数组，所以我们在主函数内调用时需要这样。
```cpp
add(x,z);
add(y+1,-z);
```
- 单点查询
我们要进行单点查操作，就需要从 $x$ 扫到 $0$，每一个修改都要加起来，就是把差分前缀和起来。
```cpp
int sum(int x){
int ans=0;
while(x){
ans+=t[x];
x-=lowbit(x);
}
return ans;
}
```
## Code
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
int t[500005];int a[500005];
int lowbit(int k){
return k& -k;
}
void add(int x,int k){
while(x<=n){
t[x]+=k;
x+=lowbit(x);
}
}
int sum(int x){
int ans=0;
while(x){
ans+=t[x];
x-=lowbit(x);
}
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
int c;
cin>>c;
if(c==1){
int x,y,z;
cin>>x>>y>>z;
add(x,z);
add(y+1,-z);
}
else{
int x;
cin>>x;
int ans=sum(x)+a[x];
cout<<ans<<endl;
}
}
return 0;
}
```