树状数组区间修改区间查询
问题——两种操作
- 给定 \(l,r,x\) ,将 \([l,r]\) 这个区间内的所有值都加上 \(x\)
- 给定 \(l,r\) 求出 \([l,r]\) 的区间和
这道题肯定要用前缀和和差分，那么大体框架可以出来了
//操作一：
update(l, x), update(r + 1, -x);
//操作二
query(r) - query(l - 1)
那么怎么将这两个东西串在一起呢？
设 \(a\) 为原数组，\(sum\) 为前缀和数组，则：
\[sum_k=\sum_{i=1}^{k}a_i \]再设 \(b\) 为差分数组，根据定义，易得：
\[a_k=\sum_{i=1}^{k}b_i \]放在一起可以得到：
\[sum_k=\sum_{i=1}^{k}\sum_{j=1}^{i}b_j \]可以发现 \(b_1\) 被使用了 \(k\) 次， \(b_2\) 被使用了 \(k-1\) 次，可以发现，对于 \(sum_k\) , \(b_i\) 被用了 \(k-i+1\) 次，所以可以把原式转化成：
\[sum_k=\sum_{i=1}^{k}b_i\times(k-i+1) \]由于 \(k+1\) 对原来的式子没有任何影响，可以提取出来，这样再转化得
\[sum_k=(k+1)\sum_{i=1}^kb_i-\sum_{i=1}^kb_i\times i \]这样我们只要分别维护 \(b_i\) 和 \(b_i \times i\) 的前缀和就可以了
对于 \(\text{update}\)
void update(int x, int k)
{
for(int i = x; i <= n; i += lowbit(i))
tr1[i] += k, tr2[i] += k * x;
}
对于 \(\text{query}\)
ll query(int x)
{
ll ans = 0;
for(int i = x; i; i -= lowbit(i))
ans += tr1[i] * (x + 1) - tr2[i];
return ans;
}