題目描述
在N（1<=N<=100000）個數A1…An組成的序列上進行M(1<=M<=100000)次操作，操作有兩種：
(1)1 x y：表示修改A[x]為y；
(1)2 x y：詢問x到y之間的最大值。

輸入
第一行輸入N(1<=N<=100000)，表示序列的長度，接下來N行輸入原始序列；接下來一行輸入M(1<=M<=100000)表示操作的次數，接下來M行，每行為1 x y或2 x y

輸出
對于每個操作(2)輸出對應的答案。

樣例輸入
5
1
2
3
4
5
3
2 1 4
1 3 5
2 2 4

樣例輸出
4
5

數據范圍限制

提示

【限制】

保證序列中的所有的數都在longint范圍內
.
.
.
.
.
.
.
.

程序:

uses math; var n,i,j,kind,x,y,m:longint; a,f:array[0..300000]of longint; procedure tree(v,l,r:longint); var mid:longint; beginmid:=(l+r) div 2;if l<r thenbegintree(v*2,l,mid);tree(v*2+1,mid+1,r);end elsebeginf[v]:=a[l];exit;end;f[v]:=max(f[v*2],f[v*2+1]); end; procedure change(v,l,r,x,y:longint); var mid:longint; beginmid:=(l+r) div 2;if l=r thenbeginf[v]:=y;exit;end;if x<=mid then change(v*2,l,mid,x,y) else change(v*2+1,mid+1,r,x,y);f[v]:=max(f[v*2],f[v*2+1]) end; function find(v,l,r,x,y:longint):longint; var mid:longint; beginmid:=(l+r) div 2;if (x=l)and(y=r) then exit(f[v]);if (x<=mid)and(y<=mid) then exit(find(v*2,l,mid,x,y));if (x<=mid)and(y>mid) then exit(max(find(v*2,l,mid,x,mid),find(v*2+1,mid+1,r,mid+1,y)));if (x>mid)and(y>mid) then exit(find(v*2+1,mid+1,r,x,y)); end; beginreadln(n);for i:=1 to n doreadln(a[i]);tree(1,1,n);readln(m);for i:=1 to m dobeginreadln(kind,x,y);if kind=1 then change(1,1,n,x,y) else writeln(find(1,1,n,x,y));end; end.

轉載于:https://www.cnblogs.com/YYC-0304/p/9499979.html

總結

以上是生活随笔為你收集整理的【线段树】最大值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。