线段树的模板

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 9 using namespace std;10 11 const int Maxn = 2e6 + 10;12 int fa[Maxn];13 struct node14 {15 int l, r;16 int value;17 int mid() {18 return (l + r) / 2;19 }20 }s[Maxn];21 void build(int i, int l, int r)22 {23 s[i].l = l;24 s[i].r = r;25 s[i].value = 0;26 while (r == l) {27 fa[l] = i;28 return;29 }30 build(i * 2, l, (l + r) / 2);31 build(i * 2 + 1, (l + r) / 2 + 1, r);32 }33 void updata(int x)34 {35 if (x == 1) return;36 int fi = x / 2;37 int a = s[fi * 2].value;38 int b = s[fi * 2 + 1].value;39 s[fi].value = max(a, b);40 updata(fi);41 }42 int Max;43 void query(int i, int l, int r)44 {45 if (s[i].l == l && s[i].r == r) {46 Max = max(Max, s[i].value);47 return;48 }49 int m = s[i].mid();50 if (r <= m) query(i << 1, l, r);51 else if (l > m) query(i << 1 | 1, l, r);52 else {53 query(i << 1, l, m);54 query(i << 1 | 1, m + 1, r);55 }56 57 }58 int main()59 {60 int n, m;61 while (scanf("%d %d", &n, &m) == 2) {62 build(1, 1, n);63 for (int i = 1;i <= n;i++) {64 int x;65 scanf("%d", &x);66 s[fa[i]].value = x;67 updata(fa[i]);68 }69 while (m--) {70 char t[10];71 int a, b;72 scanf("%s", t);73 scanf("%d %d", &a, &b);74 if (t[0] == 'Q') {75 Max = 0;76 query(1, a, b);77 printf("%d\n", Max);78 }79 else {80 s[fa[a]].value = b;81 updata(fa[a]);82 }83 }84 }85 return 0;86 }