完整模板（支持所有常见操作）
#include <bits/stdc++.h>
using namespace std;// ============ 配置区 ============
const int MAXN = 2e5 + 5; // 操作次数
const int MAXT = MAXN * 45; // 节点总数（操作数 * log(值域)，1e9约30层，留余量）
const int INF = 1e9 + 7; // 值域上限（可根据题目调整）
const int NEG_INF = -1e9 - 7; // 值域下限// ============ 节点数组 ============
int ls[MAXT], rs[MAXT]; // 左右儿子编号（0表示空）
int sum[MAXT]; // 区间和
int maxv[MAXT], minv[MAXT]; // 区间最值
int lazy_add[MAXT], lazy_set[MAXT];// 懒标记（add累加，set覆盖）
bool has_lazy_set[MAXT]; // 标记是否有set懒标记（因为set的值可能为0）
int tot = 0; // 节点计数器// ============ 基础函数 ============
// 新建节点（可初始化值）
int new_node(int val = 0) {++tot;ls[tot] = rs[tot] = 0;sum[tot] = maxv[tot] = minv[tot] = val;lazy_add[tot] = 0;lazy_set[tot] = 0;has_lazy_set[tot] = false;return tot;
}// 向上更新（合并儿子信息）
void push_up(int p) {if (!p) return;sum[p] = sum[ls[p]] + sum[rs[p]];maxv[p] = max(maxv[ls[p]], maxv[rs[p]]);minv[p] = min(minv[ls[p]], minv[rs[p]]);
}// 下传懒标记（核心）
void push_down(int p, int l, int r) {if (!p) return;if (l == r) { // 叶子节点不需要下传// 清空标记防止重复下传lazy_add[p] = 0;has_lazy_set[p] = false;return;}int mid = (l + r) >> 1;// 1. 处理 set 标记（优先级高于 add）if (has_lazy_set[p]) {// 左儿子if (!ls[p]) ls[p] = new_node(lazy_set[p]);else {sum[ls[p]] = lazy_set[p] * (mid - l + 1);maxv[ls[p]] = minv[ls[p]] = lazy_set[p];lazy_add[ls[p]] = 0;lazy_set[ls[p]] = lazy_set[p];has_lazy_set[ls[p]] = true;}// 右儿子if (!rs[p]) rs[p] = new_node(lazy_set[p]);else {sum[rs[p]] = lazy_set[p] * (r - mid);maxv[rs[p]] = minv[rs[p]] = lazy_set[p];lazy_add[rs[p]] = 0;lazy_set[rs[p]] = lazy_set[p];has_lazy_set[rs[p]] = true;}has_lazy_set[p] = false; // 清空当前标记}// 2. 处理 add 标记if (lazy_add[p] != 0) {// 左儿子if (!ls[p]) ls[p] = new_node(lazy_add[p]);else {sum[ls[p]] += lazy_add[p] * (mid - l + 1);maxv[ls[p]] += lazy_add[p];minv[ls[p]] += lazy_add[p];lazy_add[ls[p]] += lazy_add[p];}// 右儿子if (!rs[p]) rs[p] = new_node(lazy_add[p]);else {sum[rs[p]] += lazy_add[p] * (r - mid);maxv[rs[p]] += lazy_add[p];minv[rs[p]] += lazy_add[p];lazy_add[rs[p]] += lazy_add[p];}lazy_add[p] = 0; // 清空当前标记}
}
1. 单点操作
// ============ 单点更新（加/赋值） ============
// 单点增加
void update_add(int &p, int l, int r, int pos, int delta) {if (!p) p = new_node();if (l == r) {sum[p] += delta;maxv[p] += delta;minv[p] += delta;return;}int mid = (l + r) >> 1;if (pos <= mid) update_add(ls[p], l, mid, pos, delta);else update_add(rs[p], mid + 1, r, pos, delta);push_up(p);
}// 单点赋值
void update_set(int &p, int l, int r, int pos, int val) {if (!p) p = new_node();if (l == r) {sum[p] = maxv[p] = minv[p] = val;return;}int mid = (l + r) >> 1;if (pos <= mid) update_set(ls[p], l, mid, pos, val);else update_set(rs[p], mid + 1, r, pos, val);push_up(p);
}// 单点查询
int query_point(int p, int l, int r, int pos) {if (!p) return 0; // 未创建节点，返回默认值if (l == r) return sum[p];int mid = (l + r) >> 1;if (pos <= mid) return query_point(ls[p], l, mid, pos);else return query_point(rs[p], mid + 1, r, pos);
}
2. 区间操作
// ============ 区间查询 ============
// 区间求和
int query_sum(int p, int l, int r, int ql, int qr) {if (!p) return 0;if (ql <= l && r <= qr) return sum[p];push_down(p, l, r); // 查询前下传标记（为了儿子数据正确）int mid = (l + r) >> 1;int res = 0;if (ql <= mid) res += query_sum(ls[p], l, mid, ql, qr);if (qr > mid) res += query_sum(rs[p], mid + 1, r, ql, qr);return res;
}// 区间最大值
int query_max(int p, int l, int r, int ql, int qr) {if (!p) return INT_MIN;if (ql <= l && r <= qr) return maxv[p];push_down(p, l, r);int mid = (l + r) >> 1;int res = INT_MIN;if (ql <= mid) res = max(res, query_max(ls[p], l, mid, ql, qr));if (qr > mid) res = max(res, query_max(rs[p], mid + 1, r, ql, qr));return res;
}// 区间最小值
int query_min(int p, int l, int r, int ql, int qr) {if (!p) return INT_MAX;if (ql <= l && r <= qr) return minv[p];push_down(p, l, r);int mid = (l + r) >> 1;int res = INT_MAX;if (ql <= mid) res = min(res, query_min(ls[p], l, mid, ql, qr));if (qr > mid) res = min(res, query_min(rs[p], mid + 1, r, ql, qr));return res;
}// ============ 区间更新 ============
// 区间增加
void range_add(int &p, int l, int r, int ql, int qr, int delta) {if (!p) p = new_node();if (ql <= l && r <= qr) {sum[p] += delta * (r - l + 1);maxv[p] += delta;minv[p] += delta;lazy_add[p] += delta;return;}push_down(p, l, r);int mid = (l + r) >> 1;if (ql <= mid) range_add(ls[p], l, mid, ql, qr, delta);if (qr > mid) range_add(rs[p], mid + 1, r, ql, qr, delta);push_up(p);
}// 区间赋值（覆盖）
void range_set(int &p, int l, int r, int ql, int qr, int val) {if (!p) p = new_node();if (ql <= l && r <= qr) {sum[p] = val * (r - l + 1);maxv[p] = minv[p] = val;lazy_set[p] = val;has_lazy_set[p] = true;lazy_add[p] = 0; // set 覆盖 addreturn;}push_down(p, l, r);int mid = (l + r) >> 1;if (ql <= mid) range_set(ls[p], l, mid, ql, qr, val);if (qr > mid) range_set(rs[p], mid + 1, r, ql, qr, val);push_up(p);
}
3. 权值线段树特有操作（第K大/小、前驱后继）
// ============ 权值线段树（值域为 [1, INF]） ============
// 查询全局第 k 小（k从1开始）
int kth_small(int p, int l, int r, int k) {if (l == r) return l;push_down(p, l, r);int mid = (l + r) >> 1;int left_sum = sum[ls[p]]; // 左子树节点个数if (k <= left_sum) return kth_small(ls[p], l, mid, k);else return kth_small(rs[p], mid + 1, r, k - left_sum);
}// 查询全局第 k 大（k从1开始）
int kth_large(int p, int l, int r, int k) {if (l == r) return l;push_down(p, l, r);int mid = (l + r) >> 1;int right_sum = sum[rs[p]]; // 右子树节点个数if (k <= right_sum) return kth_large(rs[p], mid + 1, r, k);else return kth_large(ls[p], l, mid, k - right_sum);
}// 查询小于等于 x 的个数（排名）
int query_rank(int p, int l, int r, int x) {if (!p) return 0;if (r <= x) return sum[p]; // 整个区间都在 x 左侧int mid = (l + r) >> 1;int res = 0;if (l <= x) res += query_rank(ls[p], l, mid, x);if (mid + 1 <= x) res += query_rank(rs[p], mid + 1, r, x);return res;
}// 查询前驱（小于 x 的最大值）
int query_pre(int p, int l, int r, int x) {if (!p || sum[p] == 0) return -1; // 区间为空if (r < x) { // 整个区间都小于 x，直接找最大值return kth_large(p, l, r, sum[p]);}push_down(p, l, r);int mid = (l + r) >> 1;int res = -1;if (l < x) res = query_pre(ls[p], l, mid, x);if (res == -1 && mid + 1 < x) res = query_pre(rs[p], mid + 1, r, x);return res;
}// 查询后继（大于 x 的最小值）
int query_suf(int p, int l, int r, int x) {if (!p || sum[p] == 0) return -1;if (l > x) {return kth_small(p, l, r, 1); // 整个区间都大于 x，直接找最小值}push_down(p, l, r);int mid = (l + r) >> 1;int res = -1;if (r > x) res = query_suf(rs[p], mid + 1, r, x);if (res == -1 && mid > x) res = query_suf(ls[p], l, mid, x);return res;
}
4. 扫描线/区间染色（覆盖计数）
// ============ 区间覆盖染色（统计不同颜色段数） ============
int color[MAXT]; // 存储区间颜色，-1表示混合，0表示无色
bool has_color[MAXT]; // 标记是否被染色void push_down_color(int p) {if (!p || color[p] == -1 || color[p] == 0) return;if (!ls[p]) ls[p] = new_node();if (!rs[p]) rs[p] = new_node();color[ls[p]] = color[rs[p]] = color[p];has_color[ls[p]] = has_color[rs[p]] = true;
}void range_paint(int &p, int l, int r, int ql, int qr, int c) {if (!p) p = new_node();if (ql <= l && r <= qr) {color[p] = c;has_color[p] = true;return;}push_down_color(p);int mid = (l + r) >> 1;if (ql <= mid) range_paint(ls[p], l, mid, ql, qr, c);if (qr > mid) range_paint(rs[p], mid + 1, r, ql, qr, c);// 向上合并颜色（如果左右颜色相同则合并，否则为混合）if (has_color[ls[p]] && has_color[rs[p]] && color[ls[p]] == color[rs[p]]) {color[p] = color[ls[p]];has_color[p] = true;} else {color[p] = -1; // 混合has_color[p] = false;}
}// 查询区间是否被完全覆盖为某颜色
int query_color(int p, int l, int r, int ql, int qr) {if (!p || !has_color[p]) return -1; // 未染色或混合if (ql <= l && r <= qr) return color[p];push_down_color(p);int mid = (l + r) >> 1;int res = -1;if (ql <= mid) res = query_color(ls[p], l, mid, ql, qr);if (qr > mid) {int rc = query_color(rs[p], mid + 1, r, ql, qr);if (res == -1) res = rc;else if (res != rc) return -1; // 颜色不一致，返回混合}return res;
}
5. 常用工具函数
// ============ 清空重置（多组数据） ============
void init() {tot = 0;// 不需要 memset，因为节点 0 的所有值都是 0
}// ============ 离散化辅助（如果值域可离散化） ============
vector<int> alls; // 所有可能出现的值
int get_id(int x) {return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1;
}
// 使用离散化后值域变为 [1, alls.size()]，可大幅节省内存
6. 完整测试示例（洛谷 P3369 平衡树简化版）
int main() {ios::sync_with_stdio(false);cin.tie(0);init();int root = 0;int n;cin >> n;while (n--) {int op, x;cin >> op >> x;if (op == 1) { // 插入 xupdate_add(root, 1, INF, x, 1);} else if (op == 2) { // 删除 xupdate_add(root, 1, INF, x, -1);} else if (op == 3) { // 查询 x 的排名cout << query_rank(root, 1, INF, x - 1) + 1 << "\n";} else if (op == 4) { // 查询排名为 x 的数cout << kth_small(root, 1, INF, x) << "\n";} else if (op == 5) { // 查询 x 的前驱cout << query_pre(root, 1, INF, x) << "\n";} else if (op == 6) { // 查询 x 的后继cout << query_suf(root, 1, INF, x) << "\n";}}return 0;
}
7. 内存预估表（重要！）
| 值域范围 | 每操作新建节点数 | 操作数 | 建议 MAXT |
|---|---|---|---|
| (10^9) | ~30 | (10^5) | MAXN * 40 |
| (10^9) | ~30 | (2\times 10^5) | MAXN * 45 |
| (10^9) | ~30 | (5\times 10^5) | MAXN * 50 |
| (10^9) | ~30 | (10^6) | 考虑优化或改用离散化 |
注意：如果同时使用 push_down 中的自动建节点，节点数可能翻倍，建议 MAXT 开到 MAXN * 50 以上。
8. 常见优化技巧
// 技巧1：使用内联函数加速（竞赛必备）
inline void push_up(int p) { ... }// 技巧2：宏定义简化代码
#define ls(x) tree[x].ls
#define rs(x) tree[x].rs
// 或使用结构体封装（但速度略慢）// 技巧3：使用静态内存池（省去新建开销）
int pool[MAXT], pool_cnt = 0;
inline int new_node() { return ++pool_cnt; }// 技巧4：对于求和类题目，可只保留 sum 数组（省内存）
// 对于最值类题目，可只保留 maxv/minv
总结
这份模板涵盖了：
- ✅ 单点/区间：增、改、查（和/最值）
- ✅ 懒标记：支持区间加、区间赋值
- ✅ 权值线段树：第K大/小、排名、前驱后继
- ✅ 区间染色：覆盖统计
- ✅ 多组数据重置：
tot=0技巧
建议你将这份代码保存为 DynamicSegTree.cpp，比赛时直接复制框架，根据题目需求裁剪功能（去掉不需要的数组可以节省内存）。
如果需要某个特定操作的详细解释或变形（如二维动态开点、可持久化动态开点），随时告诉我！