线段树从入门到精通：原理、模板与常见变种全解析

线段树是信息学竞赛中最核心的数据结构之一，本文将带你从零基础到熟练掌握。

一、线段树本质
线段树是一种二叉树，每个节点代表一个区间。叶子节点存储单个元素，内部节点存储其子节点区间的合并信息（如区间和、区间最大值、区间最小值等）。

核心思想：区间分治 + 懒标记。

二、基础线段树：单点修改 + 区间查询

// 建树
void build(int p, int l, int r) {
    if (l == r) { tree[p] = a[l]; return; }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    tree[p] = tree[p << 1] + tree[p << 1 | 1];
}
// 单点修改
void update(int p, int l, int r, int pos, int val) { ... }
// 区间查询
int query(int p, int l, int r, int ql, int qr) { ... }

• 动态开点线段树（用于值域很大的情况）


• 可持久化线段树 / 主席树（查询历史版本，静态区间第k小）


• 线段树合并（dsu on tree 中常用）


• 线段树分裂


• 李超线段树（维护线段的最值）


• 吉司机线段树（Segment Tree Beats，区间取 min/max）

1. 先裸写一遍单点修改+区间查询 → 洛谷 P3372


2. 加入懒标记 → 洛谷 P3373（混合运算）


3. 主席树 → 洛谷 P3834（静态区间第k小）


4. 线段树合并 → 洛谷 P4556（雨天的尾巴）