# 概述

线段树 (segment tree) 是用来维护区间信息的数据结构，可以参考板子题【模板】线段树 1、【模板】线段树 2 及【模板】线段树 3。以上三题中，前者是后者的子集。下面，我们以区间和作为例子进行讨论。

线段树的想法是通过将长度大于 1 的区间划分成两个区间进行递归维护。这样，就可以形成一个树形结构，我们称之为线段树。对每次修改，我们需要修改 $O(\log n)$ 级别节点的值。对每一次区间信息检索，我们需要查询 $2\log n$ 级别节点的值。

# 建树

线段树存储于数组中。基于数组索引，寻找线段树各节点的左右孩子及父亲节点。下面是一些基本的定义：

int n;

int a[MAXN]; // input value

int ans[MAXN>>2]; // answer

inline int ls(int p) return p<<1; // left son

inline int rs(int p) return p<<1|1; // right son

对于完全二叉树，其左孩子的索引为 2*index , 右孩子的索引为 2*index+1 . 因此定义求左右孩子索引的函数，简化代码。 ans[] 数组存储需要维护的区间结果。 a[] 数组存储输入项。

这里注意不能写 p<<1+1 , 因为左移的运算优先级低。

建树是递归实现的。代码如下：

/**

 * p: index of tree node

 * l: left end of the segment

 * r: right end of the segment

 */

void build(int p, int l, int r) {

    if (l==r) {ans[p] = a[l]; return;}

    int mid = (l+r)>>1; // mid=(l+r)/2

    build(ls(p), l, mid);

    build(rs(p), mid+1, r);

}

调用建树时，只需要给出根节点索引 root_index = 1 , 即可实现调用 ( build(1, 1, n) ).

注意到，线段树中的索引 p 是不向用户直接开放的，仅需要通过根节点迭代寻找所需线段。

# 区间修改

朴素的线段树需要进行 $O(n\log n)$ 次区间修改。而引入懒标记后，线段树的区间修改次数会下降到 $O(\log n)$ 次。这样的代价是，在进行查询时，