P3368 题解

树状数组 1 | 树状数组 2（本题） | 修改记录

前置知识

$\operatorname{lowbit}(X)$ 表示 $X$ 在二进制下，最末尾的 $1$ 所代表的数字加上后面的 $0$ 组成的数字。

对于数 $X$ 做 lowbit 操作，在代码中可以表示为 X&(-X)。例如当 $X=76$ 时，其二进制为 $\texttt{1001100}$，则 $-X$ 在计算机用反码表示，为 $\texttt{0110100}$，将其按位与操作之后得到 $\texttt{0000100}$，后面组成的数字为 $\texttt{100}$，也就是 $\operatorname{lowbit}(X)$ 的值。

一种简单的结构，可以实现 $\mathcal{O}(1)$ 区间修改和 $\mathcal{O}(N)$ 单点查询。

令存储差分数组的数组为 $D$。修改操作，将 $[L,R]$ 增加 $K$，则需更改 $D_L\gets D_L+K$，$D_{R+1}\gets D_{R+1}-K$；查询操作需要统计前 $N$ 个数的前缀和。

算法介绍

• 对于修改操作，将 $[L,R]$ 增加 $K$，则需更改 $C_L\gets C_L+K$，$C_{R+1}\gets C_{R+1}-K$；
• 对于查询操作，查询第 $X$ 个数的值，则需要求前 $X$ 个 $C_i$ 的和。

正确性证明

注意事项

• 需要开 long long。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,a[N];
long long c[N]; // 注意 c 中的值可能超过 int 范围
int lowbit(int x){
	return x&(-x);
}
void add(int x,int k){ // 修改操作
	while(x<=n){
		c[x]+=k;
		x+=lowbit(x);
	}
	return;
}
long long sum(int x){ // 查询操作
	long long res=0;
	while(x){
		res+=c[x];
		x-=lowbit(x);
	}
	return res;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		add(i,a[i]-a[i-1]); // 按照差分含义初始化
	}
	while(m--){
		int op;cin>>op;
		if(op==1){
			int l,r,k;cin>>l>>r>>k;
			add(l,k),add(r+1,-k); // 差分操作
		}
		else{
			int x;cin>>x;
			cout<<sum(x)<<"\n"; // 前 x 个数的和
		}
	}
	return 0;
}