【算法代码】
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
const int inf=0x3f3f3f3f;
int a[maxn];
struct node {
int le,ri,mx; //mx represents the maximum value of interval [le,ri]
} tree[maxn*4]; //Segment tree needs 4 times the maxn space
void build(int k,int le,int ri) { //Create a segment tree
tree[k].le=le; //k represents the node number of segment tree
tree[k].ri=ri;
if(le==ri) {
tree[k].mx=a[le];
return;
}
int mid,lson,rson;
mid=(le+ri)/2; //The middle of the interval [le..ri]
lson=k*2; //Left child subscript
rson=k*2+1; //Right child subscript
build(lson,le,mid);
build(rson,mid+1,ri);
tree[k].mx=max(tree[lson].mx,tree[rson].mx);
}
void update(int k,int i,int v) { //Point update: Change the value of a[i] to v
if(tree[k].le==tree[k].ri && tree[k].le==i) { //Find leaf node a[i] with number i
tree[k].mx=v;
return;
}
int mid,lson,rson;
mid=(tree[k].le+tree[k].ri)/2;
lson=k*2; //Left child subscript
rson=k*2+1; //Right child subscript
if(i<=mid) update(lson,i,v); //Go to the left subtree to update
else update(rson,i,v); //Go to the right subtree to update
tree[k].mx=max(tree[lson].mx,tree[rson].mx);
}
int query(int k,int le,int ri) { //Interval query: find the maximum value of the interval [le..ri]
if(tree[k].le>=le && tree[k].ri<=ri) //Find interval [le..ri]
return tree[k].mx;
int mid,lson,rson;
mid=(tree[k].le+tree[k].ri)/2;
lson=k*2; //Left child subscript
rson=k*2+1; //Right child subscript
int iMAX=-inf; //Note: iMAX is a local variable
if(le<=mid)
iMAX=max(iMAX,query(lson,le,ri)); //Go to the left subtree to query
if(ri>mid)
iMAX=max(iMAX,query(rson,le,ri)); //Go to the right subtree to query
return iMAX;
}
void print(int k) {
if(tree[k].mx) {
cout<<k<<"\t"<<tree[k].le<<"\t"<<tree[k].ri<<"\t"<<tree[k].mx<<"\t"<<endl;
print(k<<1);
print((k<<1)+1);
}
}
int main() {
int n;
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];
build(1,1,n); //Create a segment tree
print(1);
int le,ri;
cout<<"Enter the query interval [le..ri]:"<<endl;
cin>>le>>ri;
cout<<query(1,le,ri)<<endl;
int idx,v;
cout<<"Enter id idx and value v of an element to be modified:"<<endl;
cin>>idx>>v;
update(1,idx,v); //Change the value of a[idx] to v
cout<<"Enter the query interval [le..ri] after updating:"<<endl;
cin>>le>>ri;
cout<<query(1,le,ri)<<endl;
return 0;
}
/*
in:
10
5 3 7 2 12 1 6 4 8 15
out:
1 1 10 15
2 1 5 12
4 1 3 7
8 1 2 5
16 1 1 5
17 2 2 3
9 3 3 7
5 4 5 12
10 4 4 2
11 5 5 12
3 6 10 15
6 6 8 6
12 6 7 6
24 6 6 1
25 7 7 6
13 8 8 4
7 9 10 15
14 9 9 8
15 10 10 15
Enter the query interval [le..ri]:
3 7
12
Enter id idx and value v of an element to be modified:
8 11111
Enter the query interval [le..ri] after updating:
5 9
11111
*/