P3372 【模板】线段树 1、P3368 【模板】树状数组 2

对于形如修改部分区间同时对部分区间求和一类问题，我们可以设原数组 $a[i]$ ,差分数组为 $d[i]$ ,有

a[i]=\sum_{k=1}^{i}d[k]，

当需要在区间 $[l,r]$ 加上 $v$ 时，修改 $l$ 和 $r+1$ 两点即可，问题是如何快速求出给定区间 $[1,x]$ 的和。也即求形如

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

的和。将差分数组带入得

s(x)=\sum_{i=1}^{x}\sum_{k=1}^{i}d[k].

于是

当 $x=1$ , $s(1)=d[1]$
当 $x=2$ , $s(2)=d[1]+d[1]+d[2]$
...
$s(x)=x\cdot d[1]+(x-1)\cdot d[2]+...+d[x]$

于是原式化为

s(x)=\sum_{i=1}^{x}(x-i+1)\cdot d[i].

进一步的有

s(x)=(x+1)\sum_{i=1}^{x}d[i]-\sum_{i=1}^{x}i\cdot d[i].

到这里，我们维护两个差分数组 $d[i]$ 和 $i\cdot d[i]$ 即可快速求出 $[1,x]$ 的区间和，同时支持区间修改。

如果是修改区间 $[l,r]$ 的同时求出单点 $x$ ，那就更简单了，维护一个差分数组 $d[i]$ 即可。

#include<iostream>
#define int long long

const int N = 5e5 + 10;
int d[N];
int d_i[N];

inline int lowbit(int x) { return x & -x; }

int query(int n,int d[])
{
	int sum = 0;
	while (n)
	{
		sum += d[n];
		n -= lowbit(n);
	}
	return sum;
}

void add(int n, int x,int d[])
{
	while (n < N)
	{
		d[n] += x;
		n += lowbit(n);
	}
}

signed main()
{
	std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
	int n, m;
	std::cin >> n >> m;
	int pre = 0, curr = 0;
	for (int i = 1; i <= n; i++)
	{
		std::cin >> curr;
		add(i, curr-pre,d);
		add(i, i * (curr - pre), d_i);
		pre = curr;
	}
	int op, x, y, k;
	for (int i = 1; i <= m; i++)
	{
		std::cin >> op;
		if (op == 1)
		{
			std::cin >> x >> y >> k;
			add(x, k,d);
			add(y + 1, -k,d);
			add(x, x * k, d_i);
			add(y + 1, -(y + 1) * k, d_i);
		}
		else
		{
			std::cin >> x >> y;
			std::cout << (y + 1) * query(y, d) - query(y, d_i) -
				(x * query(x - 1, d) - query(x - 1, d_i)) << '\n';
		}
	}
}