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

算法理解

对差分数组做区间修改只需要改两个端点；再用两棵树状数组把差分的前缀和转成原数组的前缀和。关键公式是 prefix(x) = sum(c1, x) * x - sum(c2, x)。

• 复杂度：修改、查询均 O(log n)。
• 注意：r + 1 不能越界；初始数组可以逐点视作区间 [i, i] 加值。

模板代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) (x&(-x))
const int N = 1e5 + 10;
int c1[N],c2[N];  
void updata(int *c,int x,int v)
{
	for (int i=x;i<=N;i+=lowbit(i))
	{
		c[i]+=v;
	}
}
int getsum(int *c,int x)
{
	int ans=0;
	for (int i=x;i>=1;i-=lowbit(i))
	{
		ans+=c[i];
	}
	return ans;
}
void solve()
{
	int n,m;
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		updata(c1,i,x);
		updata(c1,i+1,-x);
		updata(c2,i,(i-1)*x);
		updata(c2,i+1,-i*x);
	}
	while (m--)
	{
		int t;
		cin>>t;
		if (t==1)
		{
			int x,y,k;
			cin>>x>>y>>k;
			updata(c1,x,k);
			updata(c1,y+1,-k);
			updata(c2,x,k*(x-1));
			updata(c2,y+1,-k*y);
		}
		else{
			int x,y;
			cin>>x>>y;
			cout<<getsum(c1,y)*y-getsum(c2,y)-(getsum(c1,x-1)*(x-1)-getsum(c2,x-1))<<endl;
		}
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t=1;
//	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}