线段树建树的优化

建树优化

由于 $N$（数组的长度）在程序运行过程中不会发生变化（如果它会变化，那么你需要使用另一种数据结构，例如 treap），树中的每一个节点（基本上也就是 segm_tree 数组中的每一个下标）始终都会存储同一个区间的答案。

因此，在我们将要使用的实现中，不需要存储当前区间的两个端点，只需要把它们作为参数传递给所有函数即可。

建树

int t[N * 4];

void build(int p, int l, int r) {
    if (l == r) t[p] = A[l]; return; 
    int mid = (l + r) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    t[p] = max(t[p * 2], t[p * 2 + 1]);
} 

build(1, 1, n);

单点修改

void update(int p, int l, int r, int x, int v) {
    if (l == r) { t[p] = y; return; } 
    
    int mid = (l + r) / 2;
    if (x <= mid) update(2 * p, l, mid, x, v); 
    else update(2 * p + 1, mid + 1, r, x, v);
}

update(1, 1, N, x, v);

区间查询

int query(int p, int l, int r, int x, int y) {
    if (x <= l && y >= r) return t[p];

    int val = -(1 << 30);
    int mid = (l + r) / 2;
    if (x <= mid) val = max(val, query(2 * p, l, mid, x, y));
    if (y > mid)  val = max(val, query(2 * p + 1, mid + 1, r, x, y));

    return val;
}

query(1, 1, N, x, y);

节省内存的实现

如果观察数组 t，可以发现其中节点的编号顺序与 BFS 遍历（层序遍历）的顺序一致。

使用这种遍历方式，节点 $v$ 的两个子节点分别为 $2v$ 和 $2v+1$。但是，如果 $n$ 不是 $2$ 的幂，这种方法会跳过某些下标，因此数组 t 中的一部分空间不会被使用。

这种实现的内存上界为 $4n$，尽管对于一个拥有 $n$ 个元素的数组，其线段树实际上只需要 $2n-1$ 个节点。

不过，我们可以进一步减少内存占用。

按照 Euler Tour（欧拉序遍历，即先序遍历）的顺序重新给树中节点编号，并把所有节点连续存放。

考虑编号为 $v$ 的一个节点，假设它负责区间 $[l,r]$，并令 $\displaystyle mid=\frac{l+r}{2}$。显然，它的左子节点编号为 $v+1$， 左子节点负责区间 $[l,mid]$，因此左子树一共包含 $2(mid-l+1)-1$个节点。因此可以计算出 $v$ 的右子节点编号：$v+2(mid-l+1)$。

采用这种编号方式后，所需内存可以减少到 $2n$。