Alisa的数字花园

线段树

7分钟阅读

线段树 (Segment Tree)

线段树是一种用于处理区间查询和区间修改的高效数据结构，支持在 O(log n) 时间内完成各种区间操作。

核心思想

线段树是一棵完全二叉树，每个节点代表一个区间，叶子节点代表单个元素，内部节点代表子区间的合并结果。

基本性质

  • 父节点区间 = 左子树区间 ∪ 右子树区间
  • 对于节点 i：左儿子为 2*i，右儿子为 2*i+1
  • 树的高度为 O(log n)，节点总数约为 4n

基础线段树（区间查询，单点修改）

class SegmentTree {
private:
    vector<int> tree;
    int n;
 
    void build(vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, 2*node, start, mid);
            build(arr, 2*node+1, mid+1, end);
            tree[node] = tree[2*node] + tree[2*node+1];  // 区间和
        }
    }
 
    void updateHelper(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = val;
        } else {
            int mid = (start + end) / 2;
            if (idx <= mid) {
                updateHelper(2*node, start, mid, idx, val);
            } else {
                updateHelper(2*node+1, mid+1, end, idx, val);
            }
            tree[node] = tree[2*node] + tree[2*node+1];
        }
    }
 
    int queryHelper(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return 0;  // 区间不相交
        }
        if (l <= start && end <= r) {
            return tree[node];  // 区间完全包含
        }
        int mid = (start + end) / 2;
        int p1 = queryHelper(2*node, start, mid, l, r);
        int p2 = queryHelper(2*node+1, mid+1, end, l, r);
        return p1 + p2;
    }
 
public:
    SegmentTree(vector<int>& arr) {
        n = arr.size();
        tree.resize(4 * n);
        build(arr, 1, 0, n-1);
    }
 
    void update(int idx, int val) {
        updateHelper(1, 0, n-1, idx, val);
    }
 
    int query(int l, int r) {
        return queryHelper(1, 0, n-1, l, r);
    }
};

懒惰传播（Lazy Propagation）

对于区间修改操作，使用懒惰传播避免不必要的递归：

class LazySegmentTree {
private:
    vector<long long> tree, lazy;
    int n;
 
    void push(int node, int start, int end) {
        if (lazy[node] != 0) {
            tree[node] += lazy[node] * (end - start + 1);
            if (start != end) {  // 不是叶子节点
                lazy[2*node] += lazy[node];
                lazy[2*node+1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }
 
    void build(vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, 2*node, start, mid);
            build(arr, 2*node+1, mid+1, end);
            tree[node] = tree[2*node] + tree[2*node+1];
        }
    }
 
    void updateRange(int node, int start, int end, int l, int r, int val) {
        push(node, start, end);
        if (start > r || end < l) return;
 
        if (start >= l && end <= r) {
            lazy[node] += val;
            push(node, start, end);
            return;
        }
 
        int mid = (start + end) / 2;
        updateRange(2*node, start, mid, l, r, val);
        updateRange(2*node+1, mid+1, end, l, r, val);
 
        push(2*node, start, mid);
        push(2*node+1, mid+1, end);
        tree[node] = tree[2*node] + tree[2*node+1];
    }
 
    long long queryRange(int node, int start, int end, int l, int r) {
        if (start > r || end < l) return 0;
 
        push(node, start, end);
        if (start >= l && end <= r) {
            return tree[node];
        }
 
        int mid = (start + end) / 2;
        long long p1 = queryRange(2*node, start, mid, l, r);
        long long p2 = queryRange(2*node+1, mid+1, end, l, r);
        return p1 + p2;
    }
 
public:
    LazySegmentTree(vector<int>& arr) {
        n = arr.size();
        tree.resize(4 * n);
        lazy.resize(4 * n, 0);
        build(arr, 1, 0, n-1);
    }
 
    void updateRange(int l, int r, int val) {
        updateRange(1, 0, n-1, l, r, val);
    }
 
    long long query(int l, int r) {
        return queryRange(1, 0, n-1, l, r);
    }
 
    void updatePoint(int idx, int val) {
        updateRange(idx, idx, val);
    }
};

不同类型的线段树

1. 最值线段树（RMQ）

// 将 tree[node] = tree[2*node] + tree[2*node+1] 改为：
tree[node] = max(tree[2*node], tree[2*node+1]);  // 最大值
tree[node] = min(tree[2*node], tree[2*node+1]);  // 最小值

2. 乘法懒惰传播

struct LazyNode {
    long long add, mul;
    LazyNode() : add(0), mul(1) {}
};
 
void push(int node, int start, int end) {
    if (lazy[node].mul != 1 || lazy[node].add != 0) {
        tree[node] = tree[node] * lazy[node].mul + lazy[node].add * (end - start + 1);
        if (start != end) {
            // 传播到子节点
            lazy[2*node].mul *= lazy[node].mul;
            lazy[2*node].add = lazy[2*node].add * lazy[node].mul + lazy[node].add;
            lazy[2*node+1].mul *= lazy[node].mul;
            lazy[2*node+1].add = lazy[2*node+1].add * lazy[node].mul + lazy[node].add;
        }
        lazy[node] = LazyNode();  // 重置
    }
}

3. 动态开点线段树

struct Node {
    int left, right;
    long long val, lazy;
    Node() : left(-1), right(-1), val(0), lazy(0) {}
};
 
class DynamicSegmentTree {
private:
    vector<Node> nodes;
    int nodeCount;
    int L, R;  // 值域范围
 
    int newNode() {
        nodes.emplace_back();
        return nodeCount++;
    }
 
public:
    DynamicSegmentTree(int l, int r) : L(l), R(r), nodeCount(0) {
        nodes.reserve(4000000);  // 预分配空间
        newNode();  // 创建根节点
    }
 
    void update(int l, int r, int val) { updateRange(0, L, R, l, r, val); }
    long long query(int l, int r) { return queryRange(0, L, R, l, r); }
 
    // ... 其他函数实现类似，但需要动态创建节点
};

线段树应用场景

1. 区间最值查询（RMQ）

// ST表 vs 线段树
// ST表：O(n log n) 预处理，O(1) 查询，但不支持修改
// 线段树：O(n) 预处理，O(log n) 查询和修改

2. 历史最值问题

// 维护区间加法 + 历史最大值
struct HistoryMaxNode {
    long long maxVal, historyMax;
    long long addTag, historyAddTag;
};

3. 区间染色问题

// 使用懒惰传播 + 特殊标记
// lazy[node] = -1 表示无标记
// lazy[node] = color 表示整个区间都是 color 颜色

时间复杂度

  • 建树：O(n)
  • 单点修改：O(log n)
  • 区间修改：O(log n)（带懒惰传播）
  • 区间查询：O(log n)
  • 空间复杂度：O(n)

线段树 vs 其他数据结构

数据结构区间查询区间修改单点修改适用场景
树状数组O(log n)不直接支持O(log n)前缀和，逆序对
线段树O(log n)O(log n)O(log n)通用区间操作
ST 表O(1)不支持不支持静态 RMQ
分块O(√n)O(√n)O(1)平衡查询修改

常见优化技巧

  1. zkw 线段树：非递归实现，常数更小
  2. 标记永久化：某些情况下可以不下推标记
  3. 动态开点：节省空间，处理大值域
  4. 可持久化线段树：支持历史版本查询
  5. 线段树合并/分裂：处理复杂的数据结构题

关系图谱