线段树
线段树
线段树，OI中重要的数据结构，用于维护区间信息，也可以辅助维护。线段树的性能比树状数组强（但是码量大），普遍复杂度在
\(O(\log n)\) 左右。
一、基本概念
线段树是一种二叉树，也就是对于一个线段，我们会用一个二叉树来表示。比如说一个长度为4的线段，我们可以表示成这样：
这是什么意思呢？
如果你要表示线段的和，那么最上面的根节点的权值表示的是这个线段 \(1\sim 4\)
的和。根的两个儿子分别表示这个线段中 \(1\sim
2\) 的和，与 \(3\sim 4\)
的和。以此类推。
然后我们还可以的到一个性质：节点i的权值=她的左儿子权值+她的右儿子权值。因为
\(1\sim 4\) 的和就是等于 \(1\sim 2\) 的和加上 \(3\sim 4\) 的和。
根据这个思路，我们就可以建树了，我们设一个结构体
tree，tree[i].l 和 tree[i].r
分别表示这个点代表的线段的左右下标， tree[i].sum
表示这个节点表示的线段和。
我们知道，一颗二叉树，她的左儿子和右儿子编号分别是 \(p\times2\) ...
