线段树
- 线段树的每一个节点都代表一段 区间
- 线段树用于维护符合结合律的的信息 （比如区间max/min、sum、xor之类的）
- 线段树 在最坏的情况下效率低于分块（大常数）
- 关于线段树的 建树与维护
- 线段树 是一颗二叉树，对于每个父亲节点（编号i）存在两个儿子，编号分别为2i和2i+1.
1 int n; 2 int ans[MAXN*4];//开四倍空间 3 inline int ls(int p){return p<<1;}//左儿子 4 inline int rs(int p){return p<<1|1;}//右儿子
- 此处的inline可以有效防止无需入栈的信息入栈，节省时间和空间。
- 二进制位左移一位代表着数值*2，而如果左移完之后再或上1，由于左移完之后最后一位二进制位上一定会是0，所以|1等价于+1（二进制运算更快）
-
建树
1 void build(ll p,ll l,ll r) 2 { 3 if(l==r){ans[p]=a[l];return ;} 4 //如果左右区间相同，那么必然是叶子节点啦，只有叶子节点是被真实赋值的 5 ll mid=(l+r)>>1; 6 build(ls(p),l,mid); 7 build(rs(p),mid+1,r); 8 //此处由于我们采用的是二叉树，所以对于整个结构来说，可以用二分来降低复杂度，否则树形结构则没有什么明显的优化 9 push_up(p); 10 //此处由于我们是要通过子节点来维护父亲节点，所以pushup的位置应当是在回溯时。 11 }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
