2025 Summer Day1

Content：Data Structs

Date：2025.7.17

内容

并查集
ST表
线段树

关于树状数组

一维树状数组

单点修改，区间查询

对于这一类最普通的树状数组，没有什么好说的，直接维护前缀和即可。

1
struct BIT {
2
  long long tr[N];
3

4
  static int lowbit(int x) {
5
    return x & (-x);
6
  }
7

8
  void add(int pos, long long value) {
9
    for (int i = pos; i <= n; i += lowbit(i))
10
      tr[i] += value;
11
  }
12

13
  long long query(int pos) {
14
    long long retval = 0;
15
    for (int i = pos; i > 0; i -= lowbit(i))
16
      retval += tr[i];
17
    return retval;
18
  }
19
} tr;

区间修改，单点查询

这里就需要使用到差分了。记 $d[i] = arr[i] - arr[i - 1]$ ，则我们有：

arr[i] = \sum_{i=0}^{n} d[i]

后面的求和可以用树状数组维护。

1
struct BIT {
2
  long long tr[N];
3

4
  static int lowbit(int x) {
5
    return x & (-x);
6
  }
7

8
  void add(int pos, int value) {
9
    for (int i = pos; i <= n; i += lowbit(i))
10
      tr[i] += value;
11
  }
12

13
  long long query(int pos) {
14
    long long retval = 0;
15
    for (int i = pos; i > 0; i -= lowbit(i))
16
      retval += tr[i];
17
    return retval;
18
  }
19
} tr;

这一部分的代码和上面的没什么区别，区别只有 $main()$ 函数中的输入和修改。对于输入：

1
for (int i = 1; i <= n; i++) {
2
  cin >> a[i];
3
  // 这里存储的是差分后的结果，而不是 a[i]
4
  tr.add(i, a[i] - a[i - 1]);
5
}

对于修改：

1
      int l, r, x;
2
      cin >> l >> r >> x;
3

4
      // 差分数组上的区间价相当于 d[l] += v, d[r + 1] -= v;
5
      tr.add(l, x);
6
      tr.add(r + 1, -x);

区间修改，区间查询

对于区间修改，我们沿用上面的思路，接下来我们看如何区间查询。差分有如下性质：

arr[i] = \sum_{i = 0}^{n} d[i]

而我们要求的区间和可以转化为：

\begin{aligned} \sum_{i = l}^{r} arr[i] = \sum_{i = 0}^{r} arr[i] - \sum_{i = 0}^{l - 1} arr[i] \end{aligned}

所以我们的问题重新转化为了如何求解前缀和。

\begin{aligned} \sum_{i = 0}^{r} arr[i] &= \sum_{i = 0}^{r} \sum_{j = 0}^{i} d[j] \\ &= \sum_{i = 0}^{r} (r - i + 1) \cdot d[i] \\ &= \sum_{i = 0}^{r} (r + 1) \cdot d[i] - i \cdot d[i] \\ &= (r + 1) \cdot \sum_{i = 0}^{r} d[i] - \sum_{i = 0}^{r} d[i] \cdot i \\ \end{aligned}

所以我们用两个树状数组 $tr1, tr2$ 来分别维护两个和式，就解决了区间求和的问题。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 1e6 + 5;
6
int n, q, op, a[N];
7

8
int lowbit(int x) { return x & (-x); }
9

10
struct BIT {
11
  long long tr[N];
12

13
  void add(int pos, long long value) {
14
    for (int i = pos; i <= n; i += lowbit(i)) tr[i] += value;
15
  }
16

17
  long long query(int pos) {
18
    long long retval = 0;
19
    for (int i = pos; i > 0; i -= lowbit(i)) retval += tr[i];
20
    return retval;
21
  }
22
} tr1, tr2;
23

24
int main() {
25
  ios::sync_with_stdio(false);
26
  cin.tie(nullptr);
27
  cout.tie(nullptr);
28

29
  cin >> n >> q;
30

31
  for (int i = 1; i <= n; i++) {
32
    cin >> a[i];
33

34
    tr1.add(i, a[i] - a[i - 1]);
35
    tr2.add(i, 1ll * (a[i] - a[i - 1]) * i);
36
  }
37

38
  for (int i = 1; i <= q; i++) {
39
    cin >> op;
40

41
    if (op == 1) {
42
      int l, r, value;
43
      cin >> l >> r >> value;
44
      tr1.add(l, value);
45
      tr1.add(r + 1, -value);
46
      tr2.add(l, 1ll * value * l);
47
      tr2.add(r + 1, -1ll * value * (r + 1));
48
    } else if (op == 2) {
49
      int l, r;
50
      cin >> l >> r;
51

52
      long long ans = (tr1.query(r) * (r + 1) - tr2.query(r)) - (tr1.query(l - 1) * l - tr2.query(l - 1));
53

54
      cout << ans << '\n';
55
    }
56
  }
57

58
  return 0;
59
}

二维树状数组

Pre：二维前缀和

对于二维数组的前缀和有如下公式：

sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j]

对于左上角坐标为 $(a, b)$ ，右下角坐标为 $(c, d)$ 的子矩阵，其和为：

sum[c][d] - sum[a - 1][d] - sum[c][b - 1] + sum[a - 1][b - 1]

单点修改，区间查询

和一维树状数组类似，直接记 $tr[i][j]$ 为左上角坐标为 $(0, 0)$ ，右下角坐标为 $(i, j)$ 的矩阵的和。

修改和查询直接套公式。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 1 << 12 + 5;
6
int n, m, op;
7

8
struct BIT {
9
  vector<vector<long long>> tr;
10

11
  BIT() = default;
12

13
  BIT(int n, int m) {
14
    tr.assign(n + 1, vector<long long>(m + 1, 0ll));
15
  }
16

17
  static int lowbit(int x) {
18
    return x & (-x);
19
  }
20

21
  void add(int x, int y, long long value) {
22
    for (int i = x; i <= n; i += lowbit(i))
23
      for (int j = y; j <= m; j += lowbit(j))
24
        tr[i][j] += value;
25
  }
26

27
  long long query(int x, int y) {
28
    long long retval = 0;
29
    for (int i = x; i > 0; i -= lowbit(i))
30
      for (int j = y; j > 0; j -= lowbit(j))
31
        retval += tr[i][j];
32
    return retval;
33
  }
34
} tr;
35

36
int main() {
37
  ios::sync_with_stdio(false);
38
  cin.tie(nullptr);
39
  cout.tie(nullptr);
40

41
  cin >> n >> m;
42

43
  tr = BIT(n, m);
44

45
  while (cin >> op) {
46
    if (op == 1) {
47
      int x, y, value;
48
      cin >> x >> y >> value;
49

50
      tr.add(x, y, value);
51
    } else if (op == 2) {
52
      int a, b, c, d;
53

54
      cin >> a >> b >> c >> d;
55

56
      long long ans = tr.query(c, d) - tr.query(a - 1, d) - tr.query(c, b - 1) + tr.query(a - 1, b - 1);
57

58
      cout << ans << '\n';
59
    }
60
  }
61

62
  return 0;
63
}

区间修改，单点查询

我们由一维树状数组的区间修改，单点查询启发，可以考虑定义二维差分。定义二维差分数组（为避免名字冲突，这里定义为 $c[i][j]$ ） $c[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] - a[i - 1][j - 1]$ 。

证明

观察到：

arr[i][j] = sum[i][j] - sum[i - 1][j] - sum[i][j - 1] + sum[i - 1][j - 1]

所以二维差分数组 $d[i][j]$ 满足：

a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + c[i][j]

即：

c[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1]

所以我们得到了二维差分数组 $c[i][j]$ 的表达式。

跟一维差分类似地，我们可以得到子矩阵 $(a, b)$ ， $(c, d)$ 加法在差分数组中的等效替代：

\begin{aligned} sum(a, b, c, d, v) \iff & c[a][b] + v, c[c + 1][b] - v, \\ & c[a][d + 1] - v, c[c + 1][d + 1] + v \end{aligned}

代码如下：

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
int n, m, op;
6

7
struct BIT {
8
  vector<vector<long long>> tr;
9

10
  BIT() = default;
11

12
  BIT(int n, int m) {
13
    tr.assign(n + 1, vector<long long>(m + 1, 0ll));
14
  }
15

16
  static int lowbit(int x) {
17
    return x & (-x);
18
  }
19

20
  void add(int x, int y, int value) {
21
    for (int i = x; i <= n; i += lowbit(i))
22
      for (int j = y; j <= m; j += lowbit(j))
23
        tr[i][j] += value;
24
  }
25

26
  long long query(int x, int y) {
27
    long long retval = 0;
28
    for (int i = x; i > 0; i -= lowbit(i))
29
      for (int j = y; j > 0; j -= lowbit(j))
30
        retval += tr[i][j];
31
    return retval;
32
  }
33
} tr;
34

35
int main() {
36
  ios::sync_with_stdio(false);
37
  cin.tie(nullptr);
38
  cout.tie(nullptr);
39

40
  cin >> n >> m;
41

42
  tr = BIT(n, m);
43

44
  while (cin >> op) {
45
    if (op == 1) {
46
      int a, b, c, d, value;
47
      cin >> a >> b >> c >> d >> value;
48

49
      tr.add(a, b, value);
50
      tr.add(a, d + 1, -value);
51
      tr.add(c + 1, b, -value);
52
      tr.add(c + 1, d + 1, value);
53
    } else if (op == 2) {
54
      int x, y;
55
      cin >> x >> y;
56

57
      cout << tr.query(x, y) << '\n';
58
    }
59
  }
60

61
  return 0;
62
}

区间修改，区间查询

保留上面二维树状数组上区间加的操作，接下来看看如何实现区间查询。对于二维差分，我们有：

a[x][y] = \sum_{i = 0}^{x} \sum_{j = 0}^{y} d[i][j]

对于区间查询，我们用前缀和的思路转化为：

\sum_{i = a}^b \sum_{j = c}^d a[i][j] = sum[c][d] - sum[a - 1][d] - sum[b - 1][c] + sum[a - 1][b - 1];

而对于二维前缀和，我们有：

\begin{aligned} sum[a][b] &= \sum_{i = 0}^{a} \sum_{j = 0}^{b} \sum_{k = 0}^{i} \sum_{l = 0}^{j} c[k][l] \\ &= \sum_{i = 0}^{a} \sum_{j = 0}^b (a - i + 1) \cdot (b - j + 1) \cdot c[i][j] \\ &= \sum_{I = 0}^{a} \sum_{j = 0}^b (ab - a - b + 1) \cdot c[i][j] - (b + 1) \cdot i \cdot c[i][j] - (a + 1) \cdot j \cdot c[i][j] + i \cdot j \cdot c[i][j] \end{aligned}

所以用四个二维树状数组分别维护 $c[i][j]$ ， $i \cdot c[i][j$ ， $j \cdot c[i][j]$ ， $i \cdot j \cdot c[i][j]$ 就可以了。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
int n, m, op;
6

7
struct BIT {
8
  vector<vector<long long>> t1, t2, t3, t4;
9

10
  BIT() = default;
11
  BIT(int n, int m) {
12
    t1.assign(n + 1, vector<long long>(m + 1, 0ll));
13
    t2.assign(n + 1, vector<long long>(m + 1, 0ll));
14
    t3.assign(n + 1, vector<long long>(m + 1, 0ll));
15
    t4.assign(n + 1, vector<long long>(m + 1, 0ll));
16
  }
17

18
  static int lowbit(int x) {
19
    return x & (-x);
20
  }
21

22
  void add(int x, int y, long long value) {
23
    for (int i = x; i <= n; i += lowbit(i)) {
24
      for (int j = y; j <= m; j += lowbit(j)) {
25
        t1[i][j] += value;
26
        t2[i][j] += value * x;
27
        t3[i][j] += value * y;
28
        t4[i][j] += value * x * y;
29
      }
30
    }
31
  }
32

33
  long long query(int x, int y) {
34
    long long retval = 0;
35
    for (int i = x; i > 0; i -= lowbit(i)) {
36
      for (int j = y; j > 0; j -= lowbit(j)) {
37
        retval += (x + 1) * (y + 1) * t1[i][j] - (y + 1) * t2[i][j] - (x + 1) * t3[i][j] + t4[i][j];
38
      }
39
    }
40
    return retval;
41
  }
42
} tr;
43

44
int main() {
45
  ios::sync_with_stdio(false);
46
  cin.tie(nullptr);
47
  cout.tie(nullptr);
48

49
  cin >> n >> m;
50

51
  tr = BIT(n, m);
52

53
  while (cin >> op) {
54
    if (op == 1) {
55
      int a, b, c, d;
56
      long long value;
57
      cin >> a >> b >> c >> d >> value;
58

59
      tr.add(a, b, value);
60
      tr.add(c + 1, b, -value);
61
      tr.add(a, d + 1, -value);
62
      tr.add(c + 1, d + 1, value);
63
    } else if (op == 2) {
64
      int a, b, c, d;
65
      cin >> a >> b >> c >> d;
66

67
      long long ans = tr.query(c, d) - tr.query(a - 1, d) - tr.query(c, b - 1) + tr.query(a - 1, b - 1);
68

69
      cout << ans << '\n';
70
    }
71
  }
72

73
  return 0;
74
}