目录
树状数组基础
区间修改，单点查询：P3368 【模板】树状数组 2
题目描述
如题，已知一个数列，你需要进行下面两种操作：
1 x y k：将区间 \([x, y]\) 内每个数加上 \(k\)。2 x：输出第 \(x\) 个数的和。
数据范围
对于 \(100\%\) 的数据：\(1 \leq N, M\le 500000\)，\(1 \leq x, y \leq n\)，保证任意时刻序列中任意元素的绝对值都不大于 \(2^{30}\)。
区间修改，区间查询：P3372 【模板】线段树 1
题目描述
如题，已知一个数列，你需要进行下面两种操作：
1 x y k：将区间 \([x, y]\) 内每个数加上 \(k\)。2 x y：输出区间 \([x, y]\) 内每个数的和。
数据范围
对于 \(100\%\) 的数据：\(1 \le n, m \le {10}^5\)。
保证任意时刻数列中所有元素的绝对值之和 \(\le {10}^{18}\)。
分析
区间修改可以使用差分 \(D[i] = a[i]-a[i-1]\)；
区间查询，使用区间和 \(sum(l,r)=sum(r)-sum(l-1)\)；
差分的前缀和是元素组：\(a[i]=D[1]+D[2]+...+D[i]\)
\[\begin{aligned} &a[1]+a[2]+...+a[k] \\ &= D[1] + D[1]+D[2] + D[1]+D[2]+D[3] +...+ D[1]+D[2]+...+D[k]\\ &= kD[1] + (k-1)D[2] + (k-2)D[3] + ... + (k-(k-1))D[k] \\ &= k\sum_{i=1}^{k}D[i] - \sum_{i=1}^{k} {(i-1)D[i]} \end{aligned} \]通过 2 个树状数组维护 \(D[i]\) 和 \((i-1)D[i]\)
复杂度 \(O(mlogn)\)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10;
LL n,q,a[N];
LL tr1[N], tr2[N];
#define lowbit(x) (x&(-x))
void add(LL tr[],LL x,LL y) {
while(x<=n) tr[x]+=y, x+=lowbit(x);
}
LL sum(LL tr[],LL x) {
LL ans=0;
while(x) ans+=tr[x], x-=lowbit(x);
return ans;
}
int main() {
scanf("%lld%lld", &n,&q);
for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
for(int i=1; i<=n; i++) {
add(tr1, i, a[i]-a[i-1]);
add(tr2, i, (a[i]-a[i-1])*(i-1));
}
LL op,l,r,x;
while(q--) {
scanf("%lld%lld%lld", &op, &l, &r);
if(op==1) {
scanf("%lld", &x);
add(tr1, l, x), add(tr1, r+1, -x);
add(tr2, l, x*(l-1)), add(tr2, r+1, -x*(r+1-1));
} else {
LL ans=(r*sum(tr1,r)-sum(tr2,r)) - ((l-1)*sum(tr1,l-1)-sum(tr2,l-1));
printf("%lld\n", ans);
}
}
return 0;
}