hihoCoder#1077 RMQ问题再临-线段树

终于做到线段树的题了，因为建树、更新、查询都是递归操作，所以其实挺好写的。

用数组存的树，记得MAX_NODE开成两倍叶节点数大小，否则RE啊。。不要问我是怎么知道的。

代码：

  1 #include <iostream>
  2 #include <climits>
  3 using namespace std;
  4 
  5 #define MAX_NODE 2000008
  6 
  7 int N, Q;
  8 
  9 struct SegmentTree {
 10   int left[MAX_NODE];
 11   int right[MAX_NODE];
 12   int begin[MAX_NODE];
 13   int end[MAX_NODE];
 14   int value[MAX_NODE];
 15   int root;
 16   int size;
 17 
 18   void init() {
 19     size = 1;
 20     left[0] = right[0] = root = 0;
 21     value[0] = INT_MAX;
 22   }
 23 
 24   int insert(int v) {
 25     value[size] = v;
 26     size++;
 27     return size - 1;
 28   }
 29 
 30   int _build(int l, int r) {
 31     if (l > r)
 32       return 0;
 33     if (l == r) {
 34       left[l] = right[l] = 0;
 35       begin[l] = end[l] = l;
 36       return l;
 37     }
 38 
 39     int lc = _build(l, (l + r) / 2);
 40     int rc = _build((l + r) / 2 + 1, r);
 41     int me = insert(-1);
 42     left[me] = lc;
 43     right[me] = rc;
 44     begin[me] = l;
 45     end[me] = r;
 46     value[me] = min(value[lc], value[rc]);
 47 
 48     return me;
 49   }
 50 
 51   void build() {
 52     root = _build(1, size - 1);
 53   }
 54 
 55   int _query(int n, int l, int r) {
 56     if (begin[n] == l && end[n] == r)
 57       return value[n];
 58     int medium = (begin[n] + end[n]) / 2;
 59     if (r <= medium)
 60       return _query(left[n], l, r);
 61     if (l > medium)
 62       return _query(right[n], l, r);
 63     return min(_query(left[n], l, medium), _query(right[n], medium + 1, r));
 64   }
 65 
 66   int query(int l, int r) {
 67     return _query(root, l, r);
 68   }
 69 
 70   void _update(int n, int p, int v) {
 71     if (begin[n] == p && end[n] == p) {
 72       value[p] = v;
 73       return;
 74     }
 75     int medium = (begin[n] + end[n]) / 2;
 76     if (p <= medium)
 77       _update(left[n], p, v);
 78     if (p > medium)
 79       _update(right[n], p, v);
 80     value[n] = min(value[left[n]], value[right[n]]);
 81   }
 82 
 83   void update(int p, int v) {
 84     _update(root, p, v);
 85   }
 86 } st;
 87 
 88 int main() {
 89   st.init();
 90 
 91   scanf("%d", &N);
 92   for (int i = 0; i < N; i++) {
 93     int v;
 94     scanf("%d", &v);
 95     st.insert(v);
 96   }
 97 
 98   st.build();
 99 
100   scanf("%d", &Q);
101   while (Q--) {
102     int t, a, b;
103     scanf("%d%d%d", &t, &a, &b);
104     if (t)
105       st.update(a, b);
106     else
107       printf("%d
", st.query(a, b));
108   }
109 
110   return 0;
111 }