学步园

节点保存区间的最大值，父结点保存左右结点中大的那个，建树时比较下就是了

#include<stdio.h><br /> #define N 200005</p> <p>struct node {<br /> int l;<br /> int r;<br /> int max;<br /> };</p> <p>node tree[3*N];<br /> int arr[N];</p> <p>void buid_tree(int k,int left,int right)<br /> {<br /> int mid;<br /> int L,R;<br /> tree[k].l = left; tree[k].r = right;<br /> if(right - left == 1){<br /> tree[k].max = arr[left];<br /> return ;<br /> }<br /> L = 2*k; R = L+1;<br /> mid = (tree[k].l+tree[k].r)/2;<br /> buid_tree(L,left,mid);<br /> buid_tree(R,mid,right);<br /> tree[k].max = tree[L].max > tree[R].max? tree[L].max:tree[R].max;<br /> return ;<br /> }</p> <p>int tree_search(int k,int left,int right)<br /> {<br /> int mid;<br /> int L,R;<br /> int lm = 0,rm = 0;<br /> if(left <= tree[k].l && right >= tree[k].r){<br /> return tree[k].max;<br /> }<br /> mid = (tree[k].l+tree[k].r)/2;<br /> L = 2*k; R = L+1;<br /> if(left < mid) lm = tree_search(L,left,right);<br /> if(right > mid) rm = tree_search(R,left,right);<br /> return lm > rm? lm:rm;<br /> }</p> <p>void tree_insert(int k,int left,int right,int data)<br /> {<br /> int mid;<br /> int L,R;<br /> if(left <= tree[k].l && right >= tree[k].r){<br /> tree[k].max = data;<br /> return ;<br /> }<br /> mid = (tree[k].r+tree[k].l)/2;<br /> L = 2*k; R = L+1;<br /> if(left < mid) tree_insert(L,left,right,data);<br /> if(right > mid) tree_insert(R,left,right,data);<br /> tree[k].max = tree[L].max > tree[R].max? tree[L].max:tree[R].max;<br /> return ;<br /> }</p> <p>int main()<br /> {<br /> int n,m;<br /> int i;<br /> char ch;<br /> int a,b;<br /> while(scanf("%d %d",&n,&m) == 2){<br /> for(i = 1;i <= n;i++)<br /> scanf("%d",&arr[i]);<br /> buid_tree(1,1,n+1);<br /> for(i = 0;i < m;i++){<br /> getchar();<br /> ch = getchar();<br /> if(ch == 'Q'){<br /> scanf("%d %d",&a,&b);<br /> printf("%d/n",tree_search(1,a,b+1));<br /> }<br /> if(ch == 'U'){<br /> scanf("%d %d",&a,&b);<br /> tree_insert(1,a,a+1,b);<br /> }<br /> }<br /> }<br /> return 0;<br /> }