一类区间加区间询问问题的通用处理方法

整理一下这一类问题的理解方式..以便以后更容易想清楚这类问题。

你要维护一个长度为 \(n\) 的数组 \(a\),这个数组有一个初始值。有两个二维数组 \(p[c][n]\)\(q[d][n]\)

你要支持两种操作 1. 给定 \(l, r, k, x\)\(1 \le k \le c\),对每个 \(l \le i \le r\),把 \(a[i]\) 改成 \(a[i] + x\cdot p[k][i]\) 2. 给定 \(l, r, k\)\(1 \le k \le d\),求 \(\sum_{i=l}^r q[k][i]\cdot a[i]\)

这个形式的问题在一下比较复杂的树上问题的维护中很常见。大部分这样的问题中都有 \(c = 1\)\(d = 1\)

我们先来定义一棵维护一个 \(a\) 数组,支持形如 \(l,r,x\),把所有 \(l \le i\le r\)\(a[i]\) 改成 \(a[i] + x \cdot k[i]\) (\(k\) 是一个预先确定的数组) 的操作的线段树。只要记录一下每个线段树上点对应区间内 \(k\) 的和就很容易打打 tag 实现,跑起来效率和普通线段树没有什么区别。我一般是这样实现的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
struct segTree {
ll k[maxn], iv[maxn], sk[maxn << 2], sum[maxn << 2], add[maxn << 2];
void build(int l, int r, int rt) {
if (l == r) {
sk[rt] = k[l];
sum[rt] = iv[l];
return;
}
int m = (l + r) >> 1;
build(l, m, rt<<1);
build(m+1, r, rt<<1|1);
sk[rt] = sk[rt<<1] + sk[rt<<1|1];
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void modify(int rt, ll v) {
add[rt] += v;
sum[rt] += sk[rt] * v;
}
void pushDown(int rt) {
if (add[rt]) {
modify(rt<<1, add[rt]);
modify(rt<<1|1, add[rt]);
add[rt] = 0;
}
}
void upd(int p, ll v, int l, int r, int rt) {
if (l == r) {
sum[rt] += sk[rt] * v;
return;
}
int m = (l + r) >> 1;
pushDown(rt);
if (p <= m) {
upd(p, v, l, m, rt<<1);
} else {
upd(p, v, m+1, r, rt<<1|1);
}
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void upd(int L, int R, ll v, int l, int r, int rt) {
if (L <= l && r <= R) {
modify(rt, v);
return;
}
pushDown(rt);
int m = (l + r) >> 1;
if (L <= m) {
upd(L, R, v, l, m, rt<<1);
}
if (R > m) {
upd(L, R, v, m+1, r, rt<<1|1);
}
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
ll qry(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) {
return sum[rt];
}
pushDown(rt);
int m = (l + r) >> 1;
ll ret = 0;
if (L <= m) {
ret += qry(L, R, l, m, rt<<1);
}
if (R > m) {
ret += qry(L, R, m+1, r, rt<<1|1);
}
return ret;
}
};

其中 \(iv\) 数组是 \(a\) 的初始值。

下面给出一个需要开 \(c\cdot d\) 棵线段树的实现:对每个 \(1 \le x \le c, 1\le y \le d\),开一棵线段树 \((x,y)\),维护的数组即之前定义的 \(a\) 数组,\(k[i] = p[x][i]\cdot q[y][i]\)。如果有一个询问 \(l,r,y\),我们就对每个 \(x\),在线段树 \((x,y)\) 上询问区间 \(l,r\),把得到的结果加起来。这样在处理一个修改 \(l,r,x,a\) 的时候,只要对每个 \(1 \le y \le d\) 都在线段树 \((x,y)\) 更新一下就行了。