n线段树是一棵二叉树，树中的每一个结点表示了一个区间[a,b]。每一个叶子节点表示了一个单位区间。对于每一个非叶结点所表示的结点[a,b]，其左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。
除去最后一排线段树是一个满二叉树，如图
定义：
静态全局数组模拟
struct Node{
int left, right;
…
}node[MAXN*4]
一般大小开成节点数的4倍，不需要担心空间问题
指针
Struct node{
node * left;
node * right;
…
}；
建树 Build
建树时从第一个区间开始，
1 void Build(int u,int l,int r) 2 { 3 if(l==r){ //叶子节点 4 ... //一些赋值 5 } 6 int mid=(l+r)>>1; 7 Build(L(u),l,mid); //左子树 8 Build(R(u),mid+1,r); //右子数 9 pushup(u) //一般这里有一个向上更新 10 }
向上更新 Pushup
该函数就是由子结点递归回来 修改父结点中的信息
void Pushup(int u){ node[u].sum = node[L(u)].sum + node[R(u)].sum; ……. ……. return ;} 延时更新Pushdown
调用此函数时，结点中一般有个状态标志位 用来判断是否需要往下更新
覆盖一般是在查询或者更新的时候，全更新会超时
void Pushdown (int u) //延迟覆盖操作{ if (node[u].state == -1) { ... 更新父结点，左右子结点信息 } else if (node[u].state == 1) { .... 更新父结点，左右子结点信息 } else { ……… }}
更新操作 Update
void Update(int u,int left,int right,data val){ if (left<=node[u].l&&node[u].r <= right) { …….. //进行某些更改操作 return ; } Pushdown(u); // 成段更新时，这里一般都有个延时更新 int mid = (node[u].l + node[u].r)>>1; //然后就是往左 往右 或左右找区间 几乎所有的 if (right <= mid) Update(L(u),left,right,val); //线段树都这样 else if (left > mid) Update(R(u),left,right,val); else { Update(L(u),left,mid,val); Update(R(u),mid+1,right,val); } Pushup(u); //这里也一般有个向上更新}
查询操作 Query
Data Query(int u,int left,int right){ if (left <= node[u].l&&node[u].r <= right) return node[u].sum; Pushdown(u); //同update操作 视情况可有可无 int mid = (node[u].l + node[u].r)>>1; if (right <= mid) return Query(L(u),left,right); else if (left > mid) return Query(R(u),left,right); else return (Query(L(u),left,mid) + Query(R(u),mid+1,right)); Pushup(u); //同上}
这个人的博客上有很多线段树的题，大家可以参考，我们就是从这上面选题来做的
n