线段树基础与核心结构

线段树是解决区间修改与区间查询问题（如单点更新、区间加法、区间求和等）的核心数据结构。在绝大多数需要数据结构优化的场景中，线段树都是首选方案。

线段树的基本结构如下图所示：

一棵包含 \(n\) 个叶子节点的线段树共有 \(\log n\) 层，节点总数约为 \(1 + 2 + 4 + \cdots + 2^{\log n} \approx 2n\)。在实际分配数组空间时，通常需要开辟 \(4n\) 的大小，以防止因二叉树形态不完美导致的越界问题。每个节点维护其对应区间的聚合信息（如区间和），并通过左右子节点的信息合并而来。

基础区间加法与求和

使用结构体封装节点信息可以大幅提升代码的通用性和可扩展性。以下为重构后的基础线段树实现，支持区间加法与区间求和：

#include <iostream>
#include <vector>

using namespace std;

struct SegNode {
    long long sum;
    int len;
    long long lazy;

    SegNode() : sum(0), len(0), lazy(0) {}
};

const int MAXN = 100005;
int arr[MAXN];
SegNode tree[MAXN << 2];

SegNode merge_nodes(const SegNode& left, const SegNode& right) {
    SegNode res;
    res.sum = left.sum + right.sum;
    res.len = left.len + right.len;
    return res;
}

void apply_lazy(int node, long long val) {
    tree[node].lazy += val;
    tree[node].sum += 1LL * tree[node].len * val;
}

void push_down(int node) {
    if (tree[node].lazy != 0) {
        apply_lazy(node << 1, tree[node].lazy);
        apply_lazy(node << 1 | 1, tree[node].lazy);
        tree[node].lazy = 0;
    }
}

void build(int node, int l, int r) {
    if (l == r) {
        tree[node].sum = arr[l];
        tree[node].len = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(node << 1, l, mid);
    build(node << 1 | 1, mid + 1, r);
    tree[node] = merge_nodes(tree[node << 1], tree[node << 1 | 1]);
}

void range_add(int node, int l, int r, int ql, int qr, long long val) {
    if (ql <= l && r <= qr) {
        apply_lazy(node, val);
        return;
    }
    push_down(node);
    int mid = (l + r) >> 1;
    if (ql <= mid) range_add(node << 1, l, mid, ql, qr, val);
    if (qr > mid) range_add(node << 1 | 1, mid + 1, r, ql, qr, val);
    tree[node] = merge_nodes(tree[node << 1], tree[node << 1 | 1]);
}

long long range_query(int node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[node].sum;
    push_down(node);
    int mid = (l + r) >> 1;
    long long res = 0;
    if (ql <= mid) res += range_query(node << 1, l, mid, ql, qr);
    if (qr > mid) res += range_query(node << 1 | 1, mid + 1, r, ql, qr);
    return res;
}

进阶信息维护

维护区间最值

若需同时维护区间的最大值和最小值，只需在 SegNode 中增加 max_val 和 min_val 字段，并在 merge_nodes 和 apply_lazy 中同步更新即可。

维护区间平方和

当操作涉及区间加上一个常数 \(v\) 时，平方和的更新公式为：

\(\sum_{i=l}^r (x_i + v)^2 = \sum_{i=l}^r x_i^2 + 2v \sum_{i=l}^r x_i + v^2(r - l + 1)\)

在节点中增加 sum_sq 字段，下传懒标记时按上述公式更新。

乘法与加法混合（双懒标记）

处理同时包含区间乘法和加法的操作时，必须严格规定标记的生效顺序。通常采用"先乘后加"的策略，即节点的真实值表示为 \(x \times mul + add\)。下传标记时，子节点的 \(mul\) 和 \(add\) 需同步乘上父节点的 \(mul\)，子节点的 \(add\) 还需加上父节点的 \(add\)。

区间添加等差数列

给区间加上一个等差数列，等价于维护两个懒标记：首项增量 \(first\) 和公差 \(diff\)。合并时，右子节点的首项需要加上左子节点的长度乘以公差。区间和的增量可通过等差数列求和公式直接计算。

特殊区间操作与优化

最大子段和 (GSS系列)

维护最大连续子段和需要同时记录四个信息：区间总和、最大前缀和、最大后缀和、最大子段和。合并两个区间时，最大子段和可能完全在左区间、完全在右区间，或跨越中点（左区间的最大后缀和 + 右区间的最大前缀和）。

区间开方 (GSS4)

开方操作不具备线性性质，无法直接使用懒标记。但考虑到数值范围（如 \(10^{18}\)），一个数最多被开方数次就会变为 \(1\) 或 \(0\)。因此，只需在节点中维护区间最大值，当最大值 \(\le 1\) 时直接剪枝，否则递归到叶子节点进行单点修改。

取模运算优化技巧

在涉及大量取模运算的题目中，需注意以下优化细节：

• 避免全局使用 #define int long long，按需使用以防止常数过大导致超时。
• 乘法运算前必须转换为 long long，并尽量减少不必要的取模操作。
• 注意三次方运算可能会溢出 long long，需结合模数提前处理。
• 使用 if (x >= MOD) x -= MOD; 代替 % MOD 可显著提升执行速度。
• C++ 中对负数取模结果仍为负数，需手动修正为 (x % MOD + MOD) % MOD。

可持久化数据结构

可持久化数据结构允许访问历史版本，且通常要求强制在线。其核心思想是"不修改原有节点，而是创建新节点"。常见应用包括可持久化数组、可持久化并查集和可持久化线段树。

可持久化线段树（主席树）

对于单点修改操作，每次修改只会影响从根到叶子路径上的 \(\log n\) 个节点。通过新建这 \(\log n\) 个节点，并将其余未修改的子树指针直接指向历史版本，即可在 \(O(\log n)\) 的时间和空间复杂度内完成版本更新。

主席树（前缀值域可持久化线段树）常用于解决"静态区间第 \(k\) 小"问题。对数组的每个前缀建立一棵值域线段树，查询区间 \([l, r]\) 时，利用前缀和思想，通过第 \(r\) 棵树与第 \(l-1\) 棵树的节点权值作差，即可在值域上二分找到第 \(k\) 小的元素。

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

using namespace std;

struct PersistentNode {
    int left_child, right_child;
    int count;
};

const int MAXN = 100005;
const int MAX_LOG = 20;
PersistentNode nodes[MAXN * MAX_LOG];
int roots[MAXN];
int node_cnt = 0;

int build(int l, int r) {
    int idx = ++node_cnt;
    nodes[idx].count = 0;
    if (l == r) {
        nodes[idx].left_child = nodes[idx].right_child = 0;
        return idx;
    }
    int mid = (l + r) >> 1;
    nodes[idx].left_child = build(l, mid);
    nodes[idx].right_child = build(mid + 1, r);
    return idx;
}

int update(int prev_idx, int l, int r, int pos) {
    int curr_idx = ++node_cnt;
    nodes[curr_idx] = nodes[prev_idx];
    nodes[curr_idx].count++;
    if (l == r) return curr_idx;
    
    int mid = (l + r) >> 1;
    if (pos <= mid) {
        nodes[curr_idx].left_child = update(nodes[prev_idx].left_child, l, mid, pos);
    } else {
        nodes[curr_idx].right_child = update(nodes[prev_idx].right_child, mid + 1, r, pos);
    }
    return curr_idx;
}

int query_kth(int u, int v, int l, int r, int k) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int left_count = nodes[nodes[v].left_child].count - nodes[nodes[u].left_child].count;
    if (k <= left_count) {
        return query_kth(nodes[u].left_child, nodes[v].left_child, l, mid, k);
    } else {
        return query_kth(nodes[u].right_child, nodes[v].right_child, mid + 1, r, k - left_count);
    }
}

可持久化数组

实现可持久化数组有两种常见方法：

1. Vector + 二分查找：每个位置维护一个 vector，存储每次修改的时间戳和值。查询时通过二分查找找到小于等于当前时间戳的最新版本。
2. Map 映射：使用 map<pair<int, int>, int>，键为 {位置, 时间}，值为修改后的数据。查询时使用 lower_bound 定位。

其他高级算法技巧

根号分治（Threshold Partitioning）

在处理图或复杂区间问题时，可设定阈值 \(\sqrt{n}\)。将度数或关联数大于 \(\sqrt{n}\) 的节点定义为"大点"，其余为"小点"。修改小点时直接暴力更新；修改大点时，由于大点数量不超过 \(\sqrt{n}\)，可维护大点与小点之间的聚合信息，从而将复杂度控制在 \(O(\sqrt{n})\) 级别。

树上路径与斐波那契性质

在判断树上路径是否能构成三角形时，可先通过 LCA（最近公共祖先）提取路径上的节点权值。由于斐波那契数列是满足"任意三项不能构成三角形"的增长最慢的数列，若路径长度超过斐波那契数列在给定值域内的项数（通常不超过 50 项），则必然能构成三角形；否则只需将路径上的权值排序后暴力判断即可。