线段树

定义

段树是算法竞赛中常用的用来维护 区间信息 的数据结构．

线段树可以在 $O(\log N)$ 的时间复杂度内实现 单点修改、区间修改、区间查询 等操作．

基本结构与建树过程

如何使用一维数组存储树

在完全二叉树中，树可以用一维数组存储，$i$ 节点的左子节点和右子节点分别可以用 $2i$ 与 $2i+1$ 表示．

线段树将每个长度不为 $1$ 的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息．

下图，是数组a[] = {39,18,29,28,82}的求和线段树形态，建树过程：