二维线段树

ACM

直接粘贴书上的代码，就当一个积累吧。

所解决的问题

给定一个n·m的矩阵：

  • 查询\(x_1\le x\le x_2, y_1\le y \le y_2\)中的最大值和最小值
  • 将(x, y)的值改编为value

题目

Census, Uva11297

代码

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// UVa11297 Census
// Rujia Liu
#include<algorithm>
using namespace std;
const int INF = 1<<30;
const int maxn = 2000 + 10;
struct IntervalTree2D {
  int Max[maxn][maxn], Min[maxn][maxn], n, m;
  int xo, xleaf, x1, y1, x2, y2, x, y, v, vmax, vmin; // 参数、查询结果和中间变量
  void query1D(int o, int L, int R) {
    if(y1 <= L && R <= y2) {
      vmax = max(Max[xo][o], vmax); vmin = min(Min[xo][o], vmin);
    } else {
      int M = L + (R-L)/2;
      if(y1 <= M) query1D(o*2, L, M);
      if(M < y2) query1D(o*2+1, M+1, R);
    }
  }
  void query2D(int o, int L, int R) {
    if(x1 <= L && R <= x2) { xo = o; query1D(1, 1, m); }
    else {
      int M = L + (R-L)/2;
      if(x1 <= M) query2D(o*2, L, M);
      if(M < x2) query2D(o*2+1, M+1, R);
    }
  }
  void modify1D(int o, int L, int R) {
    if(L == R) {
      if(xleaf) { Max[xo][o] = Min[xo][o] = v; return; }
      Max[xo][o] = max(Max[xo*2][o], Max[xo*2+1][o]);
      Min[xo][o] = min(Min[xo*2][o], Min[xo*2+1][o]);
    } else {
      int M = L + (R-L)/2;
      if(y <= M) modify1D(o*2, L, M);
      else modify1D(o*2+1, M+1, R);
      Max[xo][o] = max(Max[xo][o*2], Max[xo][o*2+1]);
      Min[xo][o] = min(Min[xo][o*2], Min[xo][o*2+1]);
    }
  }
  void modify2D(int o, int L, int R) {
    if(L == R) { xo = o; xleaf = 1; modify1D(1, 1, m); }
    else {
      int M = L + (R-L)/2;
      if(x <= M) modify2D(o*2, L, M);
      else modify2D(o*2+1, M+1, R);
      xo = o; xleaf = 0; modify1D(1, 1, m);
    }
  }
  void query() {
    vmax = -INF; vmin = INF;
    query2D(1, 1, n);
  }
  void modify() {
    modify2D(1, 1, n);
  }
};
IntervalTree2D t;
#include<cstdio>
int main() {
  int n, m, Q, x1, y1, x2, y2, x, y, v;
  char op[10];
  scanf("%d%d", &n, &m);
  t.n = n; t.m = m;
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++) {
      scanf("%d", &t.v);
      t.x = i; t.y = j;
      t.modify();
    }
  scanf("%d", &Q);
  while(Q--) {
    scanf("%s", op);
    if(op[0] == 'q') {
      scanf("%d%d%d%d", &t.x1, &t.y1, &t.x2, &t.y2);
      t.query();
      printf("%d %d\n", t.vmax, t.vmin);
    } else {
      scanf("%d%d%d", &t.x, &t.y, &t.v);
      t.modify();
    }
  }
  return 0;
}

带build的代码

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
// UVa11297 Census：带build的版本
// Rujia Liu
#include<algorithm>
using namespace std;
const int INF = 1<<30;
const int maxn = 2000 + 10;
int A[maxn][maxn];
struct IntervalTree2D {
  int Max[maxn][maxn], Min[maxn][maxn], n, m;
  int xo, xleaf, row, x1, y1, x2, y2, x, y, v, vmax, vmin; // 参数、查询结果和中间变量
  void query1D(int o, int L, int R) {
    if(y1 <= L && R <= y2) {
      vmax = max(Max[xo][o], vmax); vmin = min(Min[xo][o], vmin);
    } else {
      int M = L + (R-L)/2;
      if(y1 <= M) query1D(o*2, L, M);
      if(M < y2) query1D(o*2+1, M+1, R);
    }
  }
  void query2D(int o, int L, int R) {
    if(x1 <= L && R <= x2) { xo = o; query1D(1, 1, m); }
    else {
      int M = L + (R-L)/2;
      if(x1 <= M) query2D(o*2, L, M);
      if(M < x2) query2D(o*2+1, M+1, R);
    }
  }
  void modify1D(int o, int L, int R) {
    if(L == R) {
      if(xleaf) { Max[xo][o] = Min[xo][o] = v; return; }
      Max[xo][o] = max(Max[xo*2][o], Max[xo*2+1][o]);
      Min[xo][o] = min(Min[xo*2][o], Min[xo*2+1][o]);
    } else {
      int M = L + (R-L)/2;
      if(y <= M) modify1D(o*2, L, M);
      else modify1D(o*2+1, M+1, R);
      Max[xo][o] = max(Max[xo][o*2], Max[xo][o*2+1]);
      Min[xo][o] = min(Min[xo][o*2], Min[xo][o*2+1]);
    }
  }
  void modify2D(int o, int L, int R) {
    if(L == R) { xo = o; xleaf = 1; modify1D(1, 1, m); }
    else {
      int M = L + (R-L)/2;
      if(x <= M) modify2D(o*2, L, M);
      else modify2D(o*2+1, M+1, R);
      xo = o; xleaf = 0; modify1D(1, 1, m);
    }
  }
  // 只构建xo为叶子（即x1=x2）的y树
  void build1D(int o, int L, int R) {
    if(L == R) Max[xo][o] = Min[xo][o] = A[row][L];
    else {
      int M = L + (R-L)/2;
      build1D(o*2, L, M);
      build1D(o*2+1, M+1, R);
      Max[xo][o] = max(Max[xo][o*2], Max[xo][o*2+1]);
      Min[xo][o] = min(Min[xo][o*2], Min[xo][o*2+1]);
    }
  }
  void build2D(int o, int L, int R) {
    if(L == R) { xo = o; row = L; build1D(1, 1, m); }
    else {
      int M = L + (R-L)/2;
      build2D(o*2, L, M);
      build2D(o*2+1, M+1, R);
      for(int i = 1; i <= m*4; i++) {
        Max[o][i] = max(Max[o*2][i], Max[o*2+1][i]);
        Min[o][i] = min(Min[o*2][i], Min[o*2+1][i]);
      }
    }
  }
  void query() {
    vmax = -INF; vmin = INF;
    query2D(1, 1, n);
  }
  void modify() {
    modify2D(1, 1, n);
  }
  void build() {
    build2D(1, 1, n);
  }
};
IntervalTree2D t;
#include<cstdio>
int main() {
  int n, m, Q, x1, y1, x2, y2, x, y, v;
  char op[10];
  scanf("%d%d", &n, &m);
  t.n = n; t.m = m;
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
      scanf("%d", &A[i][j]);
  t.build();
  scanf("%d", &Q);
  while(Q--) {
    scanf("%s", op);
    if(op[0] == 'q') {
      scanf("%d%d%d%d", &t.x1, &t.y1, &t.x2, &t.y2);
      t.query();
      printf("%d %d\n", t.vmax, t.vmin);
    } else {
      scanf("%d%d%d", &t.x, &t.y, &t.v);
      t.modify();
    }
  }
  return 0;
}

未解决的问题

本文标题:二维线段树

文章作者:Babydragon

发布时间:2018-02-28, 10:15:00

最后更新:2018-03-23, 13:32:40

原始链接:http://baolintian.github.io/2018/02/28/二维线段树/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 所解决的问题
    1. 1.1. 题目
    2. 1.2. 代码
    3. 1.3. 带build的代码
  2. 2. 未解决的问题
{{ live2d() }}