线段树

定义

线段树是一种树形数据结构，它可以快速地处理范围查询问题。

• 区间最值
• 区间gcd
• 区间和
• 区间最大子区间和

特点

• 每个节点都表示一个区间
• 子节点表示长度为长度一半的区间

1 ~ 8
1 ~ 4				5 ~ 8
1 ~ 2		3 ~ 4		5 ~ 6		7 ~ 8
1	2	3	4	5	6	7	8

存储

数组表示法，1-based。

• 子节点的索引：$2i, 2i+1$
• 父节点的索引：$\lfloor \frac{i}{2} \rfloor$

一般存储数据的 $4$ 倍的空间

struct Node {
    int l, r; // 区间左右端点
    int data = 0; // 区间数据
    int lazy = 0; // 懒标记，用于更新
};
vector<Node> tree(n * 4);

建树

步骤

• 记录区间数据
• 递归记录左右子树的区间数据

代码

void build(vector<int>& a, int rt, int l, int r){
    // 叶子节点
    if(r == l){
        tree[rt].data = a[l];
        tree[rt].l = l, tree[rt].r = r;
        tree[rt].lazy = 0;
        return;
    }
    // 递归记录左右子树的区间数据
    int mid = (l + r) >> 1;
    build(a, rt * 2, l, mid);
    build(a, rt * 2 + 1, mid + 1, r);
    // 记录区间数据
    tree[rt].lazy = 0;
    tree[rt].l = l, tree[rt].r = r;
    tree[rt].data = max(tree[rt*2].data, tree[rt*2+1].data);
}

懒标记（下放）

记录节点的更新操作，表示

• 本节点更新完毕
• 子节点未更新

步骤

当前节点有懒标记

• 执行更新操作
• 将懒标记下放到子节点
• 清空懒标记

代码

void pushDown(int rt){
    if(tree[rt].lazy){
        // 更新左子树
        tree[rt*2].data += tree[rt].lazy;
        tree[rt*2].lazy += tree[rt].lazy;
        // 更新右子树
        tree[rt*2+1].data += tree[rt].lazy;
        tree[rt*2+1].lazy += tree[rt].lazy;
        // 清空懒标记
        tree[rt].lazy = 0;
    }
}

区间查询

步骤

• 对比本区间与查询区间
  • 无交集：返回无效值
  • 完全包含：直接返回本区间数据
  • 部分包含：递归查询左右子树

代码

int query(int rt, int ql, int qr){
    // 无交集
    if(qr < tree[rt].l || ql > tree[rt].r)
        return INT_MIN;
    // 完全包含
    if(ql <= tree[rt].l && tree[rt].r <= qr)
        return tree[rt].data;
    // 先处理懒标记
    pushDown(rt);
    // 部分包含
    int Lres = query(rt * 2, ql, qr);
    int Rres = query(rt * 2 + 1, ql, qr);
    return max(Lres, Rres);
}

单点更新

步骤

• 递归找到更新点所在的子树
  • 在左半区间：更新左子树
  • 在右半区间：更新右子树
• 更新子树的区间数据

代码

void update(int rt, int idx, int val){
    // 叶子节点
    if(tree[rt].l == tree[rt].r){
        // 更新节点值并清空懒标记
        tree[rt].data = val;
        tree[rt].lazy = 0;
        return;
    }
    // 先处理懒标记
    pushDown(rt);
    // 递归更新子树
    int mid = (tree[rt].l + tree[rt].r) >> 1;
    if(idx <= mid) update(rt * 2, idx, val);
    else update(rt * 2 + 1, idx, val);
    // 更新节点值
    tree[rt].data = max(tree[rt*2].data, tree[rt*2+1].data);
}

区间更新

步骤

• 递归找到更新区间所在的子树
  • 无交集：直接返回
  • 完全包含：更新本节点
  • 部分包含：递归更新左右子树
• 更新本节点的区间数据

代码

void updateRange(int rt, int ul, int ur, int val){
    // 无交集
    if(ur < tree[rt].l || ul > tree[rt].r)
        return;
    // 完全包含
    if(ul <= tree[rt].l && tree[rt].r <= ur){
        // 更新节点值并设置懒标记
        tree[rt].data += val;
        tree[rt].lazy += val;
        return;
    }
    // 先处理懒标记
    pushDown(rt);
    // 部分包含
    updateRange(rt * 2, ul, ur, val);
    updateRange(rt * 2 + 1, ul, ur, val);
    // 更新节点值
    tree[rt].data = max(tree[rt*2].data, tree[rt*2+1].data);
}