线段树模板

SegTree.cpp

#include <cstdio>
using namespace std;
const int maxn=131072;
int seg[maxn*2+5];
int query(int x,int l,int r,int ql,int qr)
//询问[ql,qr]闭区间
{
    if (ql<=l && r<=qr) return seg[x];
    int mid=(l+r)/2,ret=0x7fffffff;//0x7fffffff=MAX_INT
    if (ql<=mid) ret=min(ret,query(x*2,l,mid,ql,qr));
    if (mid<qr) ret=min(ret,query(x*2+1,mid+1,r,ql,qr));
    return ret;
}
void edit(int x,int l,int r,int p,int v)
{
    if (l==r) seg[x]=v;
    int mid=(l+r)/2;
    if (p<=mid) edit(x*2,l,mid,p,v);
    else edit(x*2+1,mid+1,r,p,v);
    seg[x]=min(seg[x*2],seg[x*2+1]);
}
int main()
{
    /*
     * edit(1,1,n,POS,VAL) 将POS位置的数变成VAL
     * query(1,1,n,L,R) 询问[L,R]区间的区间小值
     */
    return 0;
}