树状数组区间修改区间查询

题面

首先，我们要推一个柿子。

\(\sum_{i=1}^{n} a[i]\)

把a[i]用差分数组表示出来，就可以写成

\(\sum_{i = 1}^{n}\sum_{j=1}^{i} d[i]\)

我们考虑一下，每个d[i]出现的次数是一定的。

那我们可以换一下枚举顺序，先枚举d[i]在枚举他出现的次数，就可以变成

\(\sum_{i=1}^{n} d[i]\times (n-i+1)\)

再把后面的(n-i+1）拆成(n+1) - i

就可以变成\(\sum_{i = 1}^{n} d[i] \times (n+1) - d[i] \times i\)

也就是 \(\sum_{i=1}^{n} d[i] \times (n+1)\) - \(\sum_{i=1}^{n} d[i] \times i\)

然后我们可以把前面的（n+1）提出来变成

\((n+1)\times \sum_{i=1}^{n} d[i] - \sum_{i=1}^{n} d[i] \times i\)

后面的两个前缀和就可以用树状数组来维护，这样树状数组就可以支持区间修改和区间查询。

求[l,r]的区间和可以用[1,r]的区间和减去[1,l-1]的区间和来求出来

总柿子:

\(\sum_{i=1}^{n} a_i\)

= \(\sum_{i = 1}^{n}\sum_{j=1}^{i} d_i\)

= \(\sum_{i=1}^{n} d_i\times (n-i+1)\)

= \(\sum_{i = 1}^{n} d_i \times (n+1) - d_i \times i\)

= \(\sum_{i=1}^{n} d_i \times (n+1)\) - \(\sum_{i=1}^{n} d_i \times i\)

= \((n+1)\times \sum_{i=1}^{n} d[i] - \sum_{i=1}^{n} d[i] \times i\)

代码：

#include<iostream>
#include<cstdio>
#include<cstdio>
using namespace std;
#define int long long
int n,m,opt,x,y,z,tmp;
int d[1000100],tr[1000010],a[1000010];
inline int read()
{
	int s = 0,w = 1; char ch = getchar();
	while(ch < ‘0‘ || ch > ‘9‘){if(ch == ‘-‘) w = -1; ch = getchar();}
	while(ch >= ‘0‘ && ch <= ‘9‘){s = s * 10+ch -‘0‘; ch = getchar();}
	return s * w;
}
int lowbit(int x){return x & (-x);}
void chenge(int x,int val)
{
	for(; x <= n; x += lowbit(x))
	{
		d[x] += val;
	}
}
void modify(int x,int val)
{
	for(; x <= n; x += lowbit(x))
	{
		tr[x] += val;
	}
}
int ask(int x)
{
	int ans = 0;
	for(; x>=1; x -= lowbit(x))
	{
		ans += d[x];
	}
	return ans;
}
int query(int x)
{
	int ans = 0;
	for(; x>=1; x -= lowbit(x))
	{
		ans += tr[x];
	}
	return ans;
}
signed main()
{
	n = read(); m = read();
	for(int i = 1; i <= n; i++)
	{
		a[i] = read();
		tmp = a[i] - a[i-1];
		chenge(i,tmp); modify(i,tmp * i);
	}
	while(m--)
	{
		opt = read(); x = read(); y = read();
		if(opt == 1)
		{
			z = read();
			chenge(x,z); chenge(y+1,-z);
			modify(x,x * z); modify(y+1,-(y+1) * z);
		}
		if(opt == 2)
		{
			int sum1 = (x) * ask(x-1) - query(x-1);
			int sum2 = (y+1) * ask(y) - query(y);
			printf("%lld\n",sum2-sum1); 
		}
	} 
	return 0;
}

至于二维树状数组的区间修改，区间查询，就是把差分数组改为二维差分。

但蒟蒻我还没学会，先把坑占上吧QAQ。

树状数组区间修改区间查询

原文：https://www.cnblogs.com/genshy/p/13455399.html