线段树支持的操作有：单点修改、区间查询。
类设计
一个线段树的结点包含3个元素：该区间左端点、该区间右端点、该区间维护的数值。
例如：
struct Tr{ int l,r,w; }; Tr tr[N*4];
建树
void build(int u,int l,int r){ tr[u]={l,r}; if (l==r) return; int mid=l+r>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); }
void build(int u,int l,int r){ tr[u]={l,r}; if (l==r){ tr[u].w=w[r]; return; } int mid=l+r>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); pushup(u);//给u的权重赋值 }
区间查询
int query(int u,int l,int r){ if (tr[u].l>=l&&tr[u].r<=r) return tr[u].w; int mid=tr[u].l+tr[u].r>>1; int v=0;//本示例中查询的是区间最大值 if (l<=mid) v=max(v,query(u<<1,l,r)); if (r>mid) v=max(v,query(u<<1|1,l,r)); return v; }
单点更新
void modify(int u,int x,int v){//u为结点号，x为位置，v为权值 if(tr[u].l==tr[u].r){ tr[u].w=v; return; } int mid=tr[u].l+tr[u].r>>1; if (x<=mid) modify(u<<1,x,v); else modify(u<<1|1,x,v); tr[u].w=max(tr[u<<1].w,tr[u<<1|1].w); return; }
pushup
pushup用于更新单点权值。
例如，在求一段区间的最大值时，pushup函数为:
void pushup(int u) { tr[u].w = max(tr[u << 1].w, tr[u << 1 | 1].w); }
