什么是线段树?
线段树是一种用来维护区间信息的特殊的平衡二叉查找树.
他可以在$O(\log{N})$时间复杂度内(效率贼鸡儿高)完成单点修改,区间修改,区间查询等操作.

通常来说,线段树会涉及:

  • pushup
  • build 将一段区间初始化为线段树
  • modify
  • query

.
在线段树划分过程中,通过不断修改mid节点来不断对数组进行划分,通常来说$mid=\lfloor{\dfrac{l+r}{2}}\rfloor$,直到l=r.
正常情况下,会使用一颗一维数组存储整棵树(类似堆).同时对长度为n的数组创建线段树需要4n个空间
若当前节点编号为X:

  • 父节点$\lfloor {\dfrac{x}{2}}\rfloor $
  • 左儿子 2x
  • 右儿子 2x+1
1
2
3
4
5
6
7
8
9
// build 函数
build(int u,int l,int r){
    tr[n].l = l,tr[n].r = r;
    if(l == r) return;
    int mid = (l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
}