线段树

杭电1754：http://hdu.hustoj.com/showproblem.php?pid=1754

该题为标准的线段树，线段树的基础模型如下：

总共分为三个阶段：

1.建树

建树的时候要考虑到数组的大小

void BuildTree(int i,int left ,int right){
    //（当前的数组下标，左范围，右范围）
    node[i].left = left;
    node[i].right = right;
    node[i].value = 0;
    if (left == right){
        father[left] = i;
        return;
    }
    BuildTree(i << 1, left, (int)(floor((left + right) / 2.0)));
    //建立左子树
    BuildTree((i << 1) + 1, (int)(floor((left + right) / 2.0)) + 1, right);
    //建立右子树
}

2.更新

void Update(int ri){
    //更新，从下往上更新
    if (ri == 1)
        return;
    int fi = ri / 2;
    int a = node[fi << 1].value;
    int b = node[(fi << 1) + 1].value;
    node[fi].value = max(a, b);
    Update(fi);
}

3.区间查询

void Query(int i, int l, int r){
    if (node[i].left == l && node[i].right == r){
        Max = max(Max, node[i].value);
        return;
    }
    i = i << 1;
    if (l <= node[i].right){
        if (r <= node[i].right) Query(i, l, r);
        else Query(i, l, node[i].right);
    }
    i++;
    if (r >= node[i].left){
        if (l >= node[i].left) Query(i, l, r);
        else Query(i, node[i].left, r);
    }

}

总代码：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <string>
 4 
 5 using  namespace std;
 6 const int MAXNODE = 1 << 19;
 7 const int MAXN = 2e5 + 5;
 8 
 9 struct Node{
10     int value;
11     int right, left;
12 }node[MAXNODE];
13 
14 int father[MAXN];
15 
16 void BuildTree(int i,int left ,int right){
17     //（当前的数组下标，左范围，右范围）
18     node[i].left = left;
19     node[i].right = right;
20     node[i].value = 0;
21     if (left == right){
22         father[left] = i;
23         return;
24     }
25     BuildTree(i << 1, left, (int)(floor((left + right) / 2.0)));
26     //建立左子树
27     BuildTree((i << 1) + 1, (int)(floor((left + right) / 2.0)) + 1, right);
28     //建立右子树
29 }
30 
31 void Update(int ri){
32     //更新，从下往上更新
33     if (ri == 1)
34         return;
35     int fi = ri / 2;
36     int a = node[fi << 1].value;
37     int b = node[(fi << 1) + 1].value;
38     node[fi].value = max(a, b);
39     Update(fi);
40 }
41 
42 int Max = -1 << 20;
43 void Query(int i, int l, int r){
44     if (node[i].left == l && node[i].right == r){
45         Max = max(Max, node[i].value);
46         return;
47     }
48     i = i << 1;
49     if (l <= node[i].right){
50         if (r <= node[i].right) Query(i, l, r);
51         else Query(i, l, node[i].right);
52     }
53     i++;
54     if (r >= node[i].left){
55         if (l >= node[i].left) Query(i, l, r);
56         else Query(i, node[i].left, r);
57     }
58 
59 }
60 
61 int main(){
62     int n, m;
63     ios::sync_with_stdio(false);
64     while (cin >> n >> m){
65         BuildTree(1, 1, n);
66         for (int i = 1; i <= n; i++){
67             int x;
68             cin >> x;
69             node[father[i]].value = x;
70             Update(father[i]);
71         }
72         string s;
73         while (m--){
74             int x, y;
75             cin >> s;
76             cin >> x >> y;
77             if (s == "Q"){
78                 Max = 0;
79                 Query(1, x, y);
80                 cout << Max << endl;
81             }
82             else if (s == "U"){
83                 node[father[x]].value = y;
84                 Update(father[x]);
85             }
86         }
87     }
88 //    system("pause");
89     return 0;
90 }