题解：P3374 【模板】树状数组 1
liyao2025
·
·
题解
题意：
有一个由 n 个数字组成的数列，对这个数列进行 m 次操作：
-
将第 x 个数加 k。
-
输出 [x,y] 区间内的和。
树状数组
引入
一个包含n个数的序列 2,7,1,12,5,9,\dots, 计算前 i 个数的和值，称为前缀和。
累加求前 $n$ 个数的和值需要 $O(n)$ 时间。而且若对 $a[i]$ 进行修改，则 $sum[i],sum[i+1],\dots,sum[n]$ 都需要修改，最坏的情况下需要 $O(n)$ 时间。
树状数组可以高效实现，其查询前缀和与点更新均为 $O(\log n)$。
那么树状数组是如何巧妙地实现呢？
### 正文
树状数组引入了分级管理制度，设置一个管理小组，每个管理员管理一个或多个连续的元素。例如，数列有 $9$ 个元素，分别用 $a[1],a[2],\dots,a[9]$ 存储，管理数组为 $c[]$。管理数组 $c[]$ 是树状的，因此称为树状数组。
树状数组，又称为二进制索引树 $(Binary Indexed Trees)$，通过二进制分解划分区间。那么 $c[i]$ 存储的是哪些值？
### 1.区间长度
若 $i$ 的二进制表示末尾有 $k$ 个连续的 $0$，则 $c[i]$ 存储的区间长度为 $2^k$，**从** $a[i]$ **向前数** $2^k$ **个元素**，即 $c[i]=s[i-2^k+1]+s[i-2^k+2]+,\dots,+a[i]$。
举例：
- $c[6]=a[5]+a[6]
3.查询前缀和
前 i 个元素的前缀和 sum[i] 等于 c[i] 加上 c[i] 的前驱。
### 4.点更新
若对 $a[i]$ 进行修改。
- 令 $a[i]$ 加上一个数 $z$，则只需更新 $c[i]$ 及其后继（祖先）。
- 即令这些节点都加上 $z$ 即可，无需修改其他节点。
例如，修改 $a[5]$，令其加 $2$。只需 $c[5]+2$，然后 $c[5]$ 的后继分别加 $2$，即 $c[6]+2,c[8]+2,c[16]+2,c[32]+2,\dots$。
### 5.查询区间和
若求区间和值 $a[i]+a[i+1]+,\dots,+a[j]$，则求解前 $j$ 个元素的和值减去前 $i-1$ 个元素的和值即可。即 $sum[j]-sum[i-1]$。
### 思路
套模板就行。
```cpp
#include<bits/stdc++.h>
using namespace std;
long long m,n,x,y,z;
long long a[1000005],c[1000005];
long long lowbit(long long i)//求lowbit
{
return (-i)&i;
}
void add(long long i,long long z)//添加操作
{
for(;i<=n;i+=lowbit(i))
c[i]=c[i]+z;
}
long long sum(long long i)//求和操作
{
long long s=0;
for(;i>0;i-=lowbit(i))
s+=c[i];
return s;
}
int main(){
scanf("%lld%lld",&n,&m);//输入
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
add(i,a[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&z,&x,&y);
if(z==1)add(x,y);
else printf("%lld\n",sum(y)-sum(x-1));//求区间和，输出
}
return 0;
}
```