线段树讲解
线段树讲解
背景
为了解决动态区间 R M Q RMQ RMQ（最值问题）发明的一种能够快速修改和查询的数据结构。
基本思路
线段树是一个二叉搜索树，每一个节点表示一个区间。
每个叶子节点表示一个位置上的数，一个非叶子节点的值为他的儿子的和（或最大值）。
建树代码
inline void Build_Tree (register const int p, register const int l, register const int r)
{
f[p].l = l;
f[p].r = r;
if (l == r)
{
f[p].sum = a[l];
}
register const int mid (l + r >> 1);
Build_Tree (p << 1, l, mid);
Build_Tree (p << 1 | 1, mid + 1, r);
f[p].sum = f[p << 1].sum + f[p << 1 | 1].sum;
return;
}