树状数组详解（区间修改和区间查询）

前置芝士

单点修改和区间查询
区间修改和单点查询

引入

例题：（洛谷 P3372 【模板】线段树 1）

已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数加上 $k$。
2.求出某区间每一个数的和。

这是线段树的模板题，然而我们要用树状数组去做它！

可以看出这题就像是 单点修改区间查询 和 区间修改单点查询 的升级版，好，那我们就顺着这两道题的思路继续走。

区间修改和区间查询

我们还是利用差分，可以得：

$\begin{array}{rl}\sum _{i=1}^n{a}_i& =\sum _{i=1}^n\sum _{j=1}^i{b}_j\\ & =n\times b_1+(n-1)\times b_2+...+b_n\\ & =n\times \sum _{i=1}^n{b}_i-\sum _{i=1}^n[b_i\times (i-1)]\end{array}$

方法就显而易见了：维护两个树状数组，一个维护 $\sum _{i=1}^n{b}_i$，一个维护 $\sum _{i=1}^n{b}_i\times (i-1)$。

而维护 $\sum _{i=1}^n{b}_i\times (i-1)$ 只需在把 $k$ 加到 $x$ 位置时将树状数组加 $k\ast (x-1)$ 即可。

完整代码

#include<iostream>
#include<cstdio>
#define MAXN 1000010
using namespace std;
int n,q,op,l,r,x;
int a[MAXN];
int c1[MAXN],c2[MAXN];
int lowbit(int x)
{
	return x&-x;
}
void update(int x,int k)
{
	int t=x;
	for(;x<=n;x+=lowbit(x))
	{
		c1[x]+=k;
		c2[x]+=k*(t-1);
	}
}
int query(int x)
{
	int ans=0,t=x;
	for(;x>=1;x-=lowbit(x))
		ans+=c1[x]*t-c2[x];
	return ans;
}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		update(i,a[i]-a[i-1]);
	}
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d%d",&op,&l,&r);
		if(op==1)
		{
			scanf("%d",&x);
			update(l,x);
			update(r+1,-x);
		}
		else
			printf("%d\n",query(r)-query(l-1));
	}
	return 0;
 } 

注：过线段树1得开long long