各位OIer大家好，今天蒟蒻我献丑，与大家一起探讨一下线段树的心得

线段树基础

线段树是什么

树者，枝叶者也。线段者，区间者也。线段树者，以区间为树、节点为叶者也。 ————沃兹基·朔德

通俗来讲，线段树就是将原本树上的节点全部替换成区间而已。所以说，线段树的结构基本和树一样，由此，便引出了下面的知识点：

线段树的存储和遍历

下图是一副区间为[1,10]的线段树

由此，便能推出以下性质（这个区间设为[1,n]）：

1. 整一个线段树最多（满二叉树）共有4n-1个点，可计为4n
2. 如果父节点区间是[l,r]，那么两个子节点（如果有）节点编号分别是[l,(l+r)/2]、[(l+r)/2+1,r]
3. 整个线段树共有logn层，所以时间复杂度可以粗略的计为logn

那么，如何建树也就迎刃而解了：

struct point{
    int l,r;  //左右区间端点
}tr[N*4]  //一般N为整个区间的长度

void build(int u,int l,int r){  //u存的是第几个节点，l、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); //递归处理左右子树
}

值得提一下，一个节点的编号并不是从上往下数到第几算第几的
打个比方，上图中区间为[6,6]的叶子节点数出来是第18号，但我们却存在第24号节点，这是为了查询的时候更方便（左子节点的编号是父节点的编号的2倍，右节点则比左节点大1），所以处理节点编号时通常会写u<<1和u<<1|1（建议没学过位运算的读者好好学习一下）

这个帖子就结束了，蒟蒻正在努力学习，见谅