树状数组 区间修改 & 区间查询(LOJ132)

  1. 单点修改 & 区间查询

    傻逼都会。

  2. 区间修改 & 单点查询

    假设 $a$ 数组为我们当前维护的数组,定义 $b_i = a_i - a_{i - 1}$ ,则 $a_i = \sum_{j = 1}^{i}b_j$ 。用单点修改 & 区间查询的树状数组维护 $b$ ,修改区间 $l$ 到 $r$ 只需使 $b_{l-1} + value$ 且 $b_r - value$ ,查询 $a_i$ 只需求 $\sum_{j = 1}^{i}b_j$ 。

  3. 区间修改 & 区间查询

    同 2 的假设下,求 $\sum_{i=l}^{r} a_i$ 即求 $\sum_{i=1}^{r} a_i - \sum_{i=1}^{l-1} a_i$ ,我们只需考虑如何求 $\sum_{i=1}^{k} a_i$ 。

    $\sum_{i=1}^{k} a_i = \sum_{i=1}^{k} \sum_{j=1}^{i} b_j = \sum_{i=1}^{k} b_i \times (i + 1 - x) = (k+1) \times \sum_{i=1}^{k} b_i + \sum_{i=1}^{k} (i \times b_i)$

    所以我们开两个树状数组,分别维护 $b_i$ 和 $i \times b_i$ 即可。

由于树状数组中不能有 0 我们需要将下标整体右移一位

代码

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
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int read() {
int x = 0; bool m = 0; char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') m = 1, c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (m) return -x; else return x;
}

#define lowbit(i) ((i)&(-(i)))

const int maxn = 1000010;
int n, m, l, r, x, opt, a[maxn];
ll s[maxn], c[2][maxn];

void modify(int k, ll x) {
for (int i = k; i <= n; i += lowbit(i))
c[0][i] += x, c[1][i] += x * (k + 1);
}

ll query(int k) {
ll ans = 0;
for (ll i = k; i > 0; i -= lowbit(i))
ans += c[0][i] * (k + 1) - c[1][i];
return ans;
}

int main() {

n = read(), m = read();
for (int i = 1; i <= n; i++)
a[i] = read(), s[i] = s[i - 1] + a[i];

for (int i = 1; i <= m; i++) {
opt = read();
if (opt == 1) {
l = read(), r = read(), x = read();
modify(l, x), modify(r + 1, -x);
} else {
l = read(), r = read();
printf("%lld\n", query(r + 1) - query(l) + s[r] - s[l - 1]);
}
}

return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×