线段树，是基于分治思想来维护区间的这么一种数据结构，其每个节点对应原数据的一段区间。
这里的原数据是广义的原数据，不止是数组下标，也可以是值域、操作序列抑或是时间。
我们首先需要明白它是怎样解决问题的：
考虑一个长度为 $ n $ 的序列 $ A \(，\) q $ 次操作，支持以下两种操作：
-
- 将 $ A $ 的区间 $ [ l , r ] $ 内所有元素加上 $ val $。
-
- 询问 $ A $ 的区间 $ [ l , r ] $ 内所有元素的和。即 $ \sum_{i=l}^{r}a[i] $。
假设一个 $ n = 6 , A = { 1 , 6 , 4 , 2 , 3 , 5 }$ 的情况。
我们考虑对于序列下标建立线段树 $ T $，那么它的结构是这样的：
其每个节点上的区间代表该节点对应的 $ A $ 中的下标区间。
其建立是一个分治的过程，我们对于初始区间 $ [ l , r ] $，设其中点为 $ mid = \frac{l+r}{2}$，那么它的左右儿子对应的区间就是 \([ l , mid ]\)，\([ mid + 1 , r ]\)。
那么对于左右儿子，又产生了两个相同的子问题，递归下去即可。
直到 $ l = r $，此时就是叶子节点，我们就在叶子节点上赋其原序列对应的值：
那么我们如何在其之上维护信息呢？这时就需要 push - up 操作。
push - up 即为自底向上更新信息。假设我们需要更新这个节点的信息：
只需要将其左右儿子的信息合并即可：
代码也就是这个样子的：
inline void push_up( int u ){
t[ u ] = t[ lefc( u ) ] + t[ rigc( u ) ];
}
那么对于其它节点，我们只需要做相同的操作即可。最终树会变成这个样子：
容易发现，我们只需要在分治递归回溯的时候更新该节点的信息即可，这样可以保证更新时左右儿子的信息已经被更新过。
于是建树的代码就是这个样子的：
void build( int u , int l , int r ){
if( l == r ){
t[ u ] = a[ l ];
return;
}
int mid = l + r >> 1; // >> 1 等价于 / 2 下取整
build( lefc( u ) , l , mid );
build( rigc( u ) , mid + 1 , r );
push_up( u );
}
好了，接下来如何查询呢？
假设此时我们要查询 $ A $ 中某个元素的值而不是整个区间。此时我们只需要到树的叶节点取值即可，因为叶节点中维护的值都是单个元素。
设我们询问的元素 $ x $ 下标为 $ p $，我们从根开始递归，此时有十分显然的两种情况：
-
- $ x $ 在当前节点的左子树。
-
- $ x $ 在当前节点的右子树。
如何判断呢？我们利用线段树的一个性质：如果当前节点对应的区间为 $ [ l , r ] $，左右儿子对应的区间就是 \([ l , mid ]\)，\([ mid + 1 , r ]\)，\(mid = \frac{l+r}{2}\)。
于是我们只需要将 $ p $ 与 $ mid $ 比较即可，如果 $ p \leq mid $，递归进入左子树，反之进入右子树，直到进入叶子节点，当前节点的值即为所求。
int query( int u , int l , int r , int p ){
if( l == r ) return t[ u ];
int mid = l + r >> 1;
if( p <= mid ) return query( lefc( u ) , l , mid , p );
else return query( rigc( u ) , mid + 1 , r , p );
}
受其启发，我们也可以对区间询问分类讨论：
设询问的区间为 $ [ p , q ] $，当前节点的区间为 $ [ l , r ] $，有这样几种情况：
-
- $ [ p , q ] $ 有一部分在左子树中。
-
- $ [ p , q ] $ 有一部分与右子树中。
当情况 1. 时，有 $ p <= mid $，情况 2. 时，有 $ q > mid $。并且两种情况可能同时满足。当 $ [ p , q ] $ 被 $ [ l , r ] $ 完全包含，即 $ l \leq p , q \leq r $ 时，直接返回。
举个例子：询问区间为 $ [ 2 , 5 ] $，从根节点向下查找：
发现 1. 2. 都满足：
对于 $ [ 1 , 3 ] $，1. 2. 都满足，而 $ [ 4 , 6 ] $ 则只满足条件 1.。
现在图中的节点即为查找到的节点，在回溯时累加它们即可。
int query( int u , int l , int r , int p , int q ){
if( p <= l && r <= q ) return t[ u ];
int mid = l + r >> 1;
int ret = 0;
if( L <= mid ) ret += query( lefc( u ) , l , mid , p , q );
if( R > mid ) ret += query( rigc( u ) , mid + 1 , r , p , q );
return ret;
}