这里为您整理了一份关于**线段树（Segment Tree）**的算法讲义。讲义将采用您要求的 `L[]`, `R[]`, `tree[]` 数组表示法，并结合 C++14 语言进行详细推导与代码实现，最后针对您提供的 CSES 经典题目进行分析。

---

# 算法讲义：线段树（Segment Tree）

## 1. 什么是线段树（定义）
线段树是一种**二叉搜索树**，它将一个区间划分成若干个子区间，每个节点都代表一个区间 $[L, R]$。
* **根节点**代表整个区间（例如 $[1, n]$）。
* 对于非叶子节点 $[L, R]$，其左子节点代表 $[L, mid]$，右子节点代表 $[mid + 1, r]$，其中 $mid = \lfloor \frac{L + R}{2} \rfloor$。
* **叶子节点**代表长度为 $1$ 的单点区间 $[i, i]$。

通过这种结构，线段树能够在对数时间内维护区间的各种性质（如区间和、区间最大值/最小值、区间异或值等）。

---

## 2. 工作原理
线段树的核心思想是**分治法（Divide and Conquer）**。通过将大区间不断对半分割，形成一棵高度为 $O(\log n)$ 的树：

1. **树的物理存储**：
   通常使用一维数组来模拟这棵二叉树。设当前节点编号为 `rt`：
   * 左子节点编号为 `rt << 1`（即 `rt * 2`）
   * 右子节点编号为 `rt << 1 | 1`（即 `rt * 2 + 1`）
   * 使用 `L[rt]` 和 `R[rt]` 数组分别记录节点 `rt` 所代表的区间左边界和右边界。
   * 使用 `tree[rt]` 数组存储该区间维护的值（如区间和或区间最值）。

2. **向上更新（Push Up）**：
   父节点的信息由左右两个子节点的信息合并而来。
   * 例如求和：`tree[rt] = tree[rt << 1] + tree[rt << 1 | 1]`

3. **延迟更新（Lazy Propagation / 懒标记）**：
   在进行**区间修改**时，如果每次都更新到叶子节点，单次操作的复杂度将退化为 $O(n)$。
   懒标记的思想是：**只修改覆盖到的最高层区间节点，并在此节点打上一个标记，代表“该区间已被修改，但子节点尚未更新”**。当后续查询或修改需要进入子区间时，再将标记下传（Push Down）一级。

---

## 3. 算法复杂度

### 为什么数组需要开 $4N$ 的空间？
在最坏情况下（例如 $N = 2^k + 1$），线段树的深度为 $k+1$。一棵深度为 $k+1$ 的满二叉树，其叶子节点编号可能会达到 $2^{k+2} - 1 \approx 4N$。为了防止数组越界，空间通常需要开辟 $4N$ 大小。

---

## 4. 优缺点与不足之处

### 优点
1. **高效性**：支持在 $O(\log n)$ 的时间内完成复杂的区间修改与区间查询。
2. **高通用性**：只要区间操作满足**结合律**（如：加法、乘法、最大公约数 GCD、最大/最小值、按位异或 XOR 等），都可以使用线段树维护。

### 缺点与不足
1. **空间开销较大**：需要开辟 $4N$ 甚至更大的辅助空间。相比之下，树状数组（Binary Indexed Tree）仅需要 $1N$ 的空间。
2. **实现较为繁琐**：相比于树状数组，线段树的代码量明显较多，调试难度稍大。
3. **不支持动态大小**：传统的线段树是静态建树，若区间范围极大（如 $10^9$ 级别），需要配合**动态开点**或**离散化**才能处理。

---

## 5. 核心操作与代码实现（基于 C++14）

这里我们以支持**区间加法**和**区间求和**的线段树为例，展示 `L[]`、`R[]`、`tree[]` 以及 `lazy[]` 的经典写法。

```cpp
#include <iostream>
#include <vector>

using namespace std;

// 假设原数组大小最大为 N
const int MAXN = 200005;

// 线段树数组，开 4 倍空间
int L[MAXN * 4];
int R[MAXN * 4];
long long tree[MAXN * 4];
long long lazy[MAXN * 4]; // 懒标记数组，用于区间修改

long long arr[MAXN]; // 原序列（下标从 1 开始）

// 向上更新：由子节点更新父节点的值
void pushup(int rt) {
    tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

// 向下传递：释放懒标记
void pushdown(int rt) {
    if (lazy[rt] != 0) {
        int lson = rt << 1;
        int rson = rt << 1 | 1;
        
        // 更新左子节点的值和标记
        tree[lson] += lazy[rt] * (R[lson] - L[lson] + 1);
        lazy[lson] += lazy[rt];
        
        // 更新右子节点的值和标记
        tree[rson] += lazy[rt] * (R[rson] - L[rson] + 1);
        lazy[rson] += lazy[rt];
        
        // 清空当前节点的标记
        lazy[rt] = 0;
    }
}

// 建树操作
void build(int rt, int l, int r) {
    L[rt] = l;
    R[rt] = r;
    lazy[rt] = 0;
    if (l == r) {
        tree[rt] = arr[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    pushup(rt);
}

// 单点修改：将位置 idx 的值改为 val（或加上 val）
// 注：若只做单点修改，可不使用 lazy 数组和 pushdown 函数
void update_point(int rt, int idx, long long val) {
    if (L[rt] == R[rt]) {
        tree[rt] = val; // 或者 tree[rt] += val
        return;
    }
    int mid = (L[rt] + R[rt]) >> 1;
    if (idx <= mid) {
        update_point(rt << 1, idx, val);
    } else {
        update_point(rt << 1 | 1, idx, val);
    }
    pushup(rt);
}

// 区间修改：将区间 [l, r] 的每个数都加上 val
void update_range(int rt, int l, int r, long long val) {
    if (l <= L[rt] && R[rt] <= r) {
        tree[rt] += val * (R[rt] - L[rt] + 1);
        lazy[rt] += val;
        return;
    }
    pushdown(rt); // 往下走之前，先下传当前节点的标记
    int mid = (L[rt] + R[rt]) >> 1;
    if (l <= mid) {
        update_range(rt << 1, l, r, val);
    }
    if (r > mid) {
        update_range(rt << 1 | 1, l, r, val);
    }
    pushup(rt);
}

// 区间查询：查询区间 [l, r] 的和
long long query_range(int rt, int l, int r) {
    if (l <= L[rt] && R[rt] <= r) {
        return tree[rt];
    }
    pushdown(rt); // 往下走之前，下传标记
    int mid = (L[rt] + R[rt]) >> 1;
    long long ans = 0;
    if (l <= mid) {
        ans += query_range(rt << 1, l, r);
    }
    if (r > mid) {
        ans += query_range(rt << 1 | 1, l, r);
    }
    return ans;
}
```

---

## 6. 结合 CSES 题目分析

针对您提到的 CSES Range Queries 经典题目，我们需要微调上述模板中的 **Push Up 逻辑** 以及 **维护值** [1]：

### (1) Static Range Sum Queries / Static Range Minimum Queries
* **特点**：无修改操作，仅做区间查询 [1]。
* **实现**：
  * **Sum**: 建树后，`pushup` 保持加法：`tree[rt] = tree[rt<<1] + tree[rt<<1|1]` [1]。直接进行区间查询即可。
  * **Min**: `pushup` 逻辑改为取最小值：`tree[rt] = std::min(tree[rt<<1], tree[rt<<1|1])` [1]。区间查询时，也返回子节点返回值的较小者，返回初始值可以设为一个极大值（如 `1e18`） [1]。
  * *注：对于静态区间和，前缀和是更好的选择；对于静态区间最小值，稀疏表（Sparse Table）可以达到 $O(1)$ 查询。但在练习中，使用线段树可以帮助熟悉结构。*

### (2) Dynamic Range Sum Queries / Dynamic Range Minimum Queries
* **特点**：单点修改，区间查询 [1]。
* **实现**：
  * 使用上述模板的 `update_point` 函数（无需 `lazy` 数组和 `pushdown`）。
  * **Sum**: `pushup` 用加法 [1]。
  * **Min**: `pushup` 用 `min` 函数 [1]。

### (3) Range Xor Queries
* **特点**：单点修改（或静态），区间异或查询 [1]。
* **性质**：异或（XOR）运算满足结合律（即 `(a ^ b) ^ c = a ^ (b ^ c)`），因此可以直接用线段树维护。
* **实现**：
  * `pushup` 改为：`tree[rt] = tree[rt << 1] ^ tree[rt << 1 | 1]` [1]。
  * 查询时，初始值为 `0`（因为任何数异或 `0` 都等于其自身） [1]，合并子区间的返回值使用 `^` 运算符 [1]。

### (4) Range Update Queries
* **特点**：区间增加一个值，单点查询值 [1]。
* **实现**：
  * 这是一个标准的**懒标记（Lazy Propagation）**应用。
  * 区间修改时调用 `update_range(1, l, r, val)`。
  * 单点查询位置 `k` 时，可以调用 `query_range(1, k, k)` [1]。由于有标记下传，单点值能被正确更新。

---

## 7. 示例：解决 "Dynamic Range Minimum Queries" 的完整代码

这里提供一个可以直接在 CSES 提交并通过的 C++14 完整代码。解决的是 **Dynamic Range Minimum Queries** 这一题 [1]：

```cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 设定无穷大值
const long long INF = 1e18;
const int MAXN = 200005;

int L[MAXN * 4];
int R[MAXN * 4];
long long tree[MAXN * 4];
long long arr[MAXN];

// 向上更新最小值
void pushup(int rt) {
    tree[rt] = min(tree[rt << 1], tree[rt << 1 | 1]);
}

// 建树
void build(int rt, int l, int r) {
    L[rt] = l;
    R[rt] = r;
    if (l == r) {
        tree[rt] = arr[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    pushup(rt);
}

// 单点更新：将位置 idx 的值修改为 val
void update_point(int rt, int idx, long long val) {
    if (L[rt] == R[rt]) {
        tree[rt] = val;
        return;
    }
    int mid = (L[rt] + R[rt]) >> 1;
    if (idx <= mid) {
        update_point(rt << 1, idx, val);
    } else {
        update_point(rt << 1 | 1, idx, val);
    }
    pushup(rt);
}

// 区间查询最小值
long long query_min(int rt, int l, int r) {
    // 如果当前区间被完全包含
    if (l <= L[rt] && R[rt] <= r) {
        return tree[rt];
    }
    int mid = (L[rt] + R[rt]) >> 1;
    long long ans = INF;
    if (l <= mid) {
        ans = min(ans, query_min(rt << 1, l, r));
    }
    if (r > mid) {
        ans = min(ans, query_min(rt << 1 | 1, l, r));
    }
    return ans;
}

int main() {
    // 优化输入输出
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

int n, q;
    if (!(cin >> n >> q)) return 0;

for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
    }

build(1, 1, n);

while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int k;
            long long u;
            cin >> k >> u;
            update_point(1, k, u);
        } else if (type == 2) {
            int a, b;
            cin >> a >> b;
            cout << query_min(1, a, b) << "\n";
        }
    }

return 0;
}
```

通过修改 `pushup` 函数和基本算子，您可以将此模板轻松地推广到区间和、区间异或等其他 CSES 经典区间问题中 [1]。

这里为您整理了一份关于线段树（Segment Tree）的算法讲义。讲义将采用您要求的 L[], R[], tree[] 数组表示法，并结合 C++14 语言进行详细推导与代码实现，最后针对您提供的 CSES 经典题目进行分析。

算法讲义：线段树（Segment Tree）

1. 什么是线段树（定义）

线段树是一种二叉搜索树，它将一个区间划分成若干个子区间，每个节点都代表一个区间 $[L, R]$。 * 根节点代表整个区间（例如 $[1, n]$）。 * 对于非叶子节点 $[L, R]$，其左子节点代表 $[L, mid]$，右子节点代表 $[mid + 1, r]$，其中 $mid = \lfloor \frac{L + R}{2} \rfloor$。 * 叶子节点代表长度为 $1$ 的单点区间 $[i, i]$。

通过这种结构，线段树能够在对数时间内维护区间的各种性质（如区间和、区间最大值/最小值、区间异或值等）。

2. 工作原理

线段树的核心思想是分治法（Divide and Conquer）。通过将大区间不断对半分割，形成一棵高度为 $O(\log n)$ 的树：

树的物理存储：通常使用一维数组来模拟这棵二叉树。设当前节点编号为 rt：
左子节点编号为 rt << 1（即 rt * 2）
右子节点编号为 rt << 1 | 1（即 rt * 2 + 1）
使用 L[rt] 和 R[rt] 数组分别记录节点 rt 所代表的区间左边界和右边界。
使用 tree[rt] 数组存储该区间维护的值（如区间和或区间最值）。
向上更新（Push Up）：父节点的信息由左右两个子节点的信息合并而来。
例如求和：tree[rt] = tree[rt << 1] + tree[rt << 1 | 1]
延迟更新（Lazy Propagation / 懒标记）：在进行区间修改时，如果每次都更新到叶子节点，单次操作的复杂度将退化为 $O(n)$。懒标记的思想是：只修改覆盖到的最高层区间节点，并在此节点打上一个标记，代表“该区间已被修改，但子节点尚未更新”。当后续查询或修改需要进入子区间时，再将标记下传（Push Down）一级。

3. 算法复杂度

操作	时间复杂度	说明
建树 (Build)	$O(n)$	需要遍历并初始化树中的所有节点。
单点修改 (Point Update)	$O(\log n)$	从根节点向下查找到叶子节点，并沿路更新。
区间修改 (Range Update)	$O(\log n)$	结合 Lazy 标记，仅更新关键区间。
区间查询 (Range Query)	$O(\log n)$	分解为不超过 $2 \log n$ 个线段树节点进行合并。
空间复杂度	$O(n)$	数组大小通常需要开到原序列长度 $N$ 的 $4$ 倍。

为什么数组需要开 $4N$ 的空间？

在最坏情况下（例如 $N = 2^k + 1$），线段树的深度为 $k+1$。一棵深度为 $k+1$ 的满二叉树，其叶子节点编号可能会达到 $2^{k+2} - 1 \approx 4N$。为了防止数组越界，空间通常需要开辟 $4N$ 大小。

4. 优缺点与不足之处

优点

高效性：支持在 $O(\log n)$ 的时间内完成复杂的区间修改与区间查询。
高通用性：只要区间操作满足结合律（如：加法、乘法、最大公约数 GCD、最大/最小值、按位异或 XOR 等），都可以使用线段树维护。

缺点与不足

空间开销较大：需要开辟 $4N$ 甚至更大的辅助空间。相比之下，树状数组（Binary Indexed Tree）仅需要 $1N$ 的空间。
实现较为繁琐：相比于树状数组，线段树的代码量明显较多，调试难度稍大。
不支持动态大小：传统的线段树是静态建树，若区间范围极大（如 $10^9$ 级别），需要配合动态开点或离散化才能处理。

5. 核心操作与代码实现（基于 C++14）

这里我们以支持区间加法和区间求和的线段树为例，展示 L[]、R[]、tree[] 以及 lazy[] 的经典写法。

#include <iostream>
#include <vector>

using namespace std;

// 假设原数组大小最大为 N
const int MAXN = 200005;

// 线段树数组，开 4 倍空间
int L[MAXN * 4];
int R[MAXN * 4];
long long tree[MAXN * 4];
long long lazy[MAXN * 4]; // 懒标记数组，用于区间修改

long long arr[MAXN]; // 原序列（下标从 1 开始）

// 向上更新：由子节点更新父节点的值
void pushup(int rt) {
    tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

// 向下传递：释放懒标记
void pushdown(int rt) {
    if (lazy[rt] != 0) {
        int lson = rt << 1;
        int rson = rt << 1 | 1;

        // 更新左子节点的值和标记
        tree[lson] += lazy[rt] * (R[lson] - L[lson] + 1);
        lazy[lson] += lazy[rt];

        // 更新右子节点的值和标记
        tree[rson] += lazy[rt] * (R[rson] - L[rson] + 1);
        lazy[rson] += lazy[rt];

        // 清空当前节点的标记
        lazy[rt] = 0;
    }
}

// 建树操作
void build(int rt, int l, int r) {
    L[rt] = l;
    R[rt] = r;
    lazy[rt] = 0;
    if (l == r) {
        tree[rt] = arr[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    pushup(rt);
}

// 单点修改：将位置 idx 的值改为 val（或加上 val）
// 注：若只做单点修改，可不使用 lazy 数组和 pushdown 函数
void update_point(int rt, int idx, long long val) {
    if (L[rt] == R[rt]) {
        tree[rt] = val; // 或者 tree[rt] += val
        return;
    }
    int mid = (L[rt] + R[rt]) >> 1;
    if (idx <= mid) {
        update_point(rt << 1, idx, val);
    } else {
        update_point(rt << 1 | 1, idx, val);
    }
    pushup(rt);
}

// 区间修改：将区间 [l, r] 的每个数都加上 val
void update_range(int rt, int l, int r, long long val) {
    if (l <= L[rt] && R[rt] <= r) {
        tree[rt] += val * (R[rt] - L[rt] + 1);
        lazy[rt] += val;
        return;
    }
    pushdown(rt); // 往下走之前，先下传当前节点的标记
    int mid = (L[rt] + R[rt]) >> 1;
    if (l <= mid) {
        update_range(rt << 1, l, r, val);
    }
    if (r > mid) {
        update_range(rt << 1 | 1, l, r, val);
    }
    pushup(rt);
}

// 区间查询：查询区间 [l, r] 的和
long long query_range(int rt, int l, int r) {
    if (l <= L[rt] && R[rt] <= r) {
        return tree[rt];
    }
    pushdown(rt); // 往下走之前，下传标记
    int mid = (L[rt] + R[rt]) >> 1;
    long long ans = 0;
    if (l <= mid) {
        ans += query_range(rt << 1, l, r);
    }
    if (r > mid) {
        ans += query_range(rt << 1 | 1, l, r);
    }
    return ans;
}

6. 结合 CSES 题目分析

针对您提到的 CSES Range Queries 经典题目，我们需要微调上述模板中的 Push Up 逻辑 以及 维护值 [1]：

(1) Static Range Sum Queries / Static Range Minimum Queries

特点：无修改操作，仅做区间查询 [1]。
实现：
Sum: 建树后，pushup 保持加法：tree[rt] = tree[rt<<1] + tree[rt<<1|1] [1]。直接进行区间查询即可。
Min: pushup 逻辑改为取最小值：tree[rt] = std::min(tree[rt<<1], tree[rt<<1|1]) [1]。区间查询时，也返回子节点返回值的较小者，返回初始值可以设为一个极大值（如 1e18） [1]。
注：对于静态区间和，前缀和是更好的选择；对于静态区间最小值，稀疏表（Sparse Table）可以达到 $O(1)$ 查询。但在练习中，使用线段树可以帮助熟悉结构。

(2) Dynamic Range Sum Queries / Dynamic Range Minimum Queries

特点：单点修改，区间查询 [1]。
实现：
使用上述模板的 update_point 函数（无需 lazy 数组和 pushdown）。
Sum: pushup 用加法 [1]。
Min: pushup 用 min 函数 [1]。

(3) Range Xor Queries

特点：单点修改（或静态），区间异或查询 [1]。
性质：异或（XOR）运算满足结合律（即 (a ^ b) ^ c = a ^ (b ^ c)），因此可以直接用线段树维护。
实现：
pushup 改为：tree[rt] = tree[rt << 1] ^ tree[rt << 1 | 1] [1]。
查询时，初始值为 0（因为任何数异或 0 都等于其自身） [1]，合并子区间的返回值使用 ^ 运算符 [1]。

(4) Range Update Queries

特点：区间增加一个值，单点查询值 [1]。
实现：
这是一个标准的懒标记（Lazy Propagation）应用。
区间修改时调用 update_range(1, l, r, val)。
单点查询位置 k 时，可以调用 query_range(1, k, k) [1]。由于有标记下传，单点值能被正确更新。

7. 示例：解决 "Dynamic Range Minimum Queries" 的完整代码

这里提供一个可以直接在 CSES 提交并通过的 C++14 完整代码。解决的是 Dynamic Range Minimum Queries 这一题 [1]：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 设定无穷大值
const long long INF = 1e18;
const int MAXN = 200005;

int L[MAXN * 4];
int R[MAXN * 4];
long long tree[MAXN * 4];
long long arr[MAXN];

// 向上更新最小值
void pushup(int rt) {
    tree[rt] = min(tree[rt << 1], tree[rt << 1 | 1]);
}

// 建树
void build(int rt, int l, int r) {
    L[rt] = l;
    R[rt] = r;
    if (l == r) {
        tree[rt] = arr[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    pushup(rt);
}

// 单点更新：将位置 idx 的值修改为 val
void update_point(int rt, int idx, long long val) {
    if (L[rt] == R[rt]) {
        tree[rt] = val;
        return;
    }
    int mid = (L[rt] + R[rt]) >> 1;
    if (idx <= mid) {
        update_point(rt << 1, idx, val);
    } else {
        update_point(rt << 1 | 1, idx, val);
    }
    pushup(rt);
}

// 区间查询最小值
long long query_min(int rt, int l, int r) {
    // 如果当前区间被完全包含
    if (l <= L[rt] && R[rt] <= r) {
        return tree[rt];
    }
    int mid = (L[rt] + R[rt]) >> 1;
    long long ans = INF;
    if (l <= mid) {
        ans = min(ans, query_min(rt << 1, l, r));
    }
    if (r > mid) {
        ans = min(ans, query_min(rt << 1 | 1, l, r));
    }
    return ans;
}

int main() {
    // 优化输入输出
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
    }

    build(1, 1, n);

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int k;
            long long u;
            cin >> k >> u;
            update_point(1, k, u);
        } else if (type == 2) {
            int a, b;
            cin >> a >> b;
            cout << query_min(1, a, b) << "\n";
        }
    }

    return 0;
}

通过修改 pushup 函数和基本算子，您可以将此模板轻松地推广到区间和、区间异或等其他 CSES 经典区间问题中 [1]。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com