二维线段树区域修改，最大值最小值

 1 /*
 2 初始化调用build(1,1,n); n为边长
 3 Modify(int x,int y,int val); 将点x，y处的值修改为val;
 4 queryMax(1, x1, x2, y1, y2);
 5 queryMin(1, x1, x2, y1, y2);
 6 x1 <= x2 y1 <= y2，表示矩形区域; 所有的坐标都是闭区间S
 7 x1, x2, y1, y1分别表示上界，下界，左界， 右界
 8 */
 9 const int INF = 0x3f3f3f3f;
10 const int maxn = 805;
11 struct Nodey {
12     int l, r;
13     int Max, Min;
14 };
15 int locy[maxn], locx[maxn];
16 struct Nodex {
17     int l, r;
18     Nodey sty[maxn * 4];
19     void build(int i, int _l, int _r) {
20         sty[i].l = _l;
21         sty[i].r = _r;
22         sty[i].Max = -INF;
23         sty[i].Min = INF;
24         if(_l == _r) {
25             locy[_l] = i;
26             return;
27         }
28         int mid = (_l + _r) / 2;
29         build(i << 1, _l, mid);
30         build((i << 1) | 1, mid + 1, _r);
31     }
32     int queryMin(int i, int _l, int _r) {
33         if(sty[i].l == _l && sty[i].r == _r)
34             return sty[i].Min;
35         int mid = (sty[i].l + sty[i].r) / 2;
36         if(_r <= mid) return queryMin(i << 1, _l, _r);
37         else if(_l > mid) return queryMin((i << 1) | 1, _l, _r);
38         else return min(queryMin(i <<1, _l, mid), queryMin((i << 1) | 1, mid + 1, _r));
39     }
40     int queryMax(int i, int _l, int _r) {
41         if(sty[i].l == _l && sty[i].r == _r)
42             return sty[i].Max;
43         int mid = (sty[i].l + sty[i].r) / 2;
44         if(_r <= mid) return queryMax(i << 1, _l, _r);
45         else if(_l > mid) return queryMax((i << 1) | 1, _l, _r);
46         else return max(queryMax(i <<1, _l, mid), queryMax((i << 1) | 1, mid + 1, _r));
47     }
48 } stx[maxn * 4];
49 int n;
50 void build(int i, int l, int r) {
51     stx[i].l = l;
52     stx[i].r = r;
53     stx[i].build(1, 1, n);
54     if(l == r) {
55         locx[l] = i;
56         return;
57     }
58     int mid = (l + r) / 2;
59     build(i << 1, l, mid);
60     build((i << 1)| 1, mid + 1, r);
61 }
62 void Modify(int x, int y, int val) {
63     int tx = locx[x];
64     int ty = locy[y];
65     stx[tx].sty[ty].Min = stx[tx].sty[ty].Max = val;
66     for(int i = tx ; i ; i >>= 1)
67         for(int j = ty ; j ; j >>= 1) {
68             if(i == tx && j == ty) continue;
69             if(j == ty) {
70                 stx[i].sty[j].Min = min(stx[i << 1].sty[j].Min, stx[(i << 1) | 1].sty[j].Min);
71                 stx[i].sty[j].Max = max(stx[i << 1].sty[j].Max, stx[(i << 1) | 1].sty[j].Max);
72             }
73             else {
74                 stx[i].sty[j].Min = min(stx[i].sty[j << 1].Min, stx[i].sty[(j << 1) | 1].Min);
75                 stx[i].sty[j].Max = max(stx[i].sty[j << 1].Max, stx[i].sty[(j << 1) | 1].Max);
76             }
77         }
78 }
79 int queryMin(int i, int x1, int x2, int y1, int y2) {
80     if(stx[i].l == x1 && stx[i].r == x2)
81         return stx[i].queryMin(1, y1, y2);
82     int mid = (stx[i].l + stx[i].r) / 2;
83     if(x2 <= mid) return queryMin(i << 1, x1, x2, y1, y2);
84     else if(x1 > mid) return queryMin((i << 1) | 1, x1, x2, y1, y2);
85     else return min(queryMin(i << 1, x1, mid, y1, y2), queryMin((i << 1) | 1, mid + 1, x2, y1, y2));
86 }
87 int queryMax(int i, int x1, int x2, int y1, int y2) {
88     if(stx[i].l == x1 && stx[i].r == x2)
89         return stx[i].queryMax(1, y1, y2);
90     int mid = (stx[i].l + stx[i].r) / 2;
91     if(x2 <= mid) return queryMax(i << 1, x1, x2, y1, y2);
92     else if(x1 > mid) return queryMax((i << 1) | 1, x1, x2, y1, y2);
93     else return max(queryMax(i << 1, x1, mid, y1, y2), queryMax((i << 1) | 1, mid + 1, x2, y1, y2));
94 }