I hate it （线段树）

目录

 

模板：

最值：

建树：

更新：

查询：

区间和：

建树：

更新：

查询：

I hate it

代码:

---

模板：

最值：

建树：

void build_tree(int node,int start,int end){

       if(start == end){   

              tree[node] = arr[start];

              return ;

       }

       int mid = (start+end)>>1;

       int left_node = 2*node+1;

       int right_node = 2*node+2;

       build_tree(left_node,start,mid);

       build_tree(right_node,mid+1,end);

       tree[node] = max(tree[left_node],tree[right_node]);

       return ;

}

更新：

void update_tree(int node,int start,int end,int idx,int val){

       if(start == end){

              tree[node] = val;

              arr[idx] = val;

              return ;

       }

       int mid = (start+end)/2;

       int left_node = 2*node+1;

       int right_node = 2*node+2;

       if(idx >= start&&idx <= mid)

              update_tree(left_node,start,mid,idx,val);

       else

              update_tree(right_node,mid+1,end,idx,val);

       tree[node] = max(tree[left_node],tree[right_node]);

}

查询：

int query_tree(int node,int start,int end,int l,int r){

       if(start == end&&start >= l&&end <= r){

              return tree[node];

       }

       if(start >= l&&end <= r){

              return tree[node];

       }

       if(l > end||r < start){

              return 0;

       }

       int mid = (start+end)>>1;

       int left_node = 2*node+1;

       int right_node = 2*node+2;

       int max_left = query_tree(left_node,start,mid,l,r);

       int max_right = query_tree(right_node,mid+1,end,l,r);   

       return max(max_left,max_right);

}

区间和：

建树：

void build_tree(int node,int start,int end,int deep){

       if(start == end){

              tree[node] = arr[start];

              tot = max(tot,deep);

              return ;

       }

       int mid = (start+end)/2;

       int left_node = 2*node+1;

       int right_node = 2*node+2;

       build_tree(left_node,start,mid,deep+1);

       build_tree(right_node,mid+1,end,deep+1);

       tree[node] = tree[left_node]+tree[right_node];

       return ;

}

更新：

void update_tree(int node,int start,int end,int idx,int val){

       if(start == end){

              tree[node] = val;

              arr[idx] = val;

              return ;

       }

       int mid = (start+end)/2;

       int left_node = 2*node+1;

       int right_node = 2*node+2;

       if(idx >= start&&idx <= mid)

              update_tree(left_node,start,mid,idx,val);

       else

              update_tree(right_node,mid+1,end,idx,val);

       tree[node] = tree[left_node]+tree[right_node];

}

查询：

int query_tree(int node,int start,int end,int l,int r){

       if(start == end){

              return tree[node];

       }

       if(l > end|| r < start){

              return 0;

       }

       if(start >=l&&r >= end){

              return tree[node];

       }

       int mid = (start+end)/2;

       int left_node = 2*node+1;

       int right_node = 2*node+2;

       int sum_left = query_tree(left_node,start,mid,l,r);

       int sum_right = query_tree(right_node,mid+1,end,l,r);

       return sum_left+sum_right;

}

I hate it

代码:

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<stdlib.h>



using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

const int maxn = 1e6+100;

int arr[maxn];

int tree[maxn<<2];

int n,m;

void build_tree(int node,int start,int end){

       if(start == end){   

              tree[node] = arr[start];

              return ;

       }

       int mid = (start+end)>>1;

       int left_node = 2*node+1;

       int right_node = 2*node+2;

       build_tree(left_node,start,mid);

       build_tree(right_node,mid+1,end);

       tree[node] = max(tree[left_node],tree[right_node]);

       return ;

}

int query_tree(int node,int start,int end,int l,int r){

       if(start == end&&start >= l&&end <= r){

              return tree[node];

       }

       if(start >= l&&end <= r){

              return tree[node];

       }

       if(l > end||r < start){

              return 0;

       }

       int mid = (start+end)>>1;

       int left_node = 2*node+1;

       int right_node = 2*node+2;

       int max_left = query_tree(left_node,start,mid,l,r);

       int max_right = query_tree(right_node,mid+1,end,l,r);   

       return max(max_left,max_right);

}

void update_tree(int node,int start,int end,int idx,int val){

       if(start == end){

              tree[node] = val;

              arr[idx] = val;

              return ;

       }

       int mid = (start+end)/2;

       int left_node = 2*node+1;

       int right_node = 2*node+2;

       if(idx >= start&&idx <= mid)

              update_tree(left_node,start,mid,idx,val);

       else

              update_tree(right_node,mid+1,end,idx,val);

       tree[node] = max(tree[left_node],tree[right_node]);

}

int main(){

       while(cin >> n >> m){

              for(int i = 0;i < n;i++){

                     cin >> arr[i];

              }            

              build_tree(0,0,n-1);

              while(m--){

                     char c;

                     cin >> c;

                     if(c == 'Q'){

                            int l,r;

                            cin >> l >> r;

                            cout << query_tree(0,0,n-1,l-1,r-1) << endl;                       

                     }

                     else if (c == 'U'){

                            int idx,val;

                            cin >> idx >> val;

                            if(arr[idx-1] > val) continue;

                            update_tree(0,0,n-1,idx-1,val);

                     }

              }

             

       }

       return 0;

}