线段树非延迟标记法
本方法与采用树状数组完全相同,只是做了下转换,采用线段树。
原问题要求数据结构支持两两种操作:
- 区间查询
- 区间修改
我们知道通常的线段树可以支持区间查询和单点修改,若想支持区间修改可以采用差分的思想。
设原数组为a,差分数组b[i]=a[i]−a[i−1],线段树的叶子节点保存差分数组b。
区间修改操作:区间[l,r]加上d,则有b[l]+=d,b[r+1]−=d。
区间查询:
n∑i=1ai=n∑i=1i∑j=1bj=(n+1)n∑i=1bi−n∑i=1i∗bi
因此线段树中保存∑bi和∑ibi两个信息。
代码:
#include <iostream>
using namespace std;
const int N = 100010;
typedef long long LL;
struct SegmentTree {
int l, r;
LL sum, dat;
} t[4 * N];
LL a[N], n, m;
void pushup(SegmentTree &u, SegmentTree &l, SegmentTree &r) {
u.sum = l.sum + r.sum;
u.dat = l.dat + r.dat;
}
void pushup(int u) {
pushup(t[u], t[2 * u], t[2 * u + 1]);
}
void update(int u, int x, LL v) {
if (t[u].l == t[u].r) t[u].sum += v, t[u].dat += x * v;
else {
int mid = t[u].l + t[u].r >> 1;
if (x <= mid) update(2 * u, x, v);
else update(2 * u + 1, x, v);
pushup(u);
}
}
SegmentTree query(int u, int l, int r) {
if (l <= t[u].l && t[u].r <= r) return t[u];
int mid = t[u].l + t[u].r >> 1;
if (r <= mid) return query(2 * u, l, r);
else if (l > mid) return query(2 * u + 1, l, r);
SegmentTree res;
SegmentTree left = query(2 * u, l, mid), right = query(2 * u + 1, mid + 1, r);
pushup(res, left, right);
return res;
}
void build(int u, int l, int r) {
if (l == r) t[u] = {l, r, a[l] - a[l - 1], (a[l] - a[l - 1]) * l};
else {
t[u] = {l, r};
int mid = l + r >> 1;
build(2 * u, l, mid), build(2 * u + 1, mid + 1, r);
pushup(u);
}
}
LL get(int x) {
if (x == 0) return 0;
SegmentTree r = query(1, 1, x);
return (x + 1) * r.sum - r.dat;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) scanf("%lld", a + i);
build(1, 1, n);
while (m--) {
char str[2];
scanf("%s", str);
if (str[0] == 'Q') {
int l, r;
scanf("%d%d", &l, &r);
printf("%lld\n", get(r) - get(l - 1));
} else {
int l, r, d;
scanf("%d%d%d", &l, &r, &d);
update(1, l, d);
if (r + 1 <= n) update(1, r + 1, -d);
}
}
return 0;
}