1 问题
在整数坐标
若按整个坐标范围建立普通线段树,需要数十亿个叶子。但若修改次数很少,真正需要保存的只是被修改位置及其祖先。
2 按需建树
动态开点仍按相同规则二分区间,只在修改经过某个尚不存在的节点时分配空间。
节点编号由分配顺序决定,不能再用 lc[p]、rc[p] 保存左右孩子编号。编号 root 保存根编号。
图用较小值域
3 修改与查询
单点加沿坐标所属的分支向下走。若当前节点为空,先分配节点;沿途总和增加修改量,直到叶子。
查询遇到空节点直接返回
修改增量可以为负,和也可以回到零。代码不会因此删除节点:值为零与节点不存在是两件事。
4 正确性
每次修改只会改变包含该坐标的区间。沿路径创建节点并累加增量,恰好更新所有受影响区间;未创建的子树没有接受过任何修改,仍表示全零。
查询在完整覆盖处使用已维护的总和,在空子树处使用初始总和零,其他部分递归分解。因此返回目标坐标区间内全部修改的累计值。
5 节点池
设整数值域长度为
估计。实际路径会共享已有祖先,通常少于这个上界。
本篇 int 孩子数组加一个 long long 总和数组,约占
6 代码
第一行操作数
1 x v:坐标的值加 。 2 l r:查询整数坐标的和。
所有坐标位于 long long 范围内。
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
typedef long long ll;
const int maxq = 100000;
// 当前值域的根到叶子至多 32 个节点,按最多 maxq 次修改预留。
const int maxnode = maxq * 32 + 5;
const ll minx = -1000000000LL, maxx = 1000000000LL;
// 0 表示空节点;lc、rc 显式保存孩子编号,不能再用 2p、2p+1。
int root, tot, lc[maxnode], rc[maxnode];
// 初始全零,空子树的区间和为 0;tr[p] 保存已发生修改的累计和。
ll tr[maxnode];
// 节点池按顺序分配,断言避免超出预留容量;全局数组初值为 0。
int new_node() {
assert(tot + 1 < maxnode);
return ++tot;
}
// 引用参数 p 把新编号写回 root 或孩子数组;只创建修改经过的路径。
void add(int &p, ll l, ll r, ll pos, ll v) {
if (!p) p = new_node();
tr[p] += v; // 当前区间包含 pos,其总和也增加 v
if (l == r) return;
ll mid = l + (r - l) / 2;
if (pos <= mid) add(lc[p], l, mid, pos, v);
else add(rc[p], mid + 1, r, pos, v);
}
// 查询 [L,R] 的和;查询过程只读,不分配任何节点。
ll query(int p, ll l, ll r, ll L, ll R) {
if (!p || r < L || R < l) return 0; // 空子树仍为全零,或没有交集
if (L <= l && r <= R) return tr[p];
ll mid = l + (r - l) / 2;
return query(lc[p], l, mid, L, R) + query(rc[p], mid + 1, r, L, R);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
int op;
ll x, y;
cin >> op >> x >> y;
// 1 x v:坐标 x 加 v;2 l r:查询坐标区间和。
if (op == 1) add(root, minx, maxx, x, y);
else cout << query(root, minx, maxx, x, y) << '\n';
}
return 0;
}
输入:
8
1 -1000000000 5
1 7 -3
2 -1000000000 0
1 1000000000 9
2 -1000000000 1000000000
2 8 999999999
1 7 3
2 7 7
输出:
5
11
0
0
7 复杂度与限制
单次修改、查询为
本篇只处理单点加。增加区间修改时,需要另行设计懒标记和下传时的节点分配;不能把单点模板直接当成区间修改模板。
空节点的返回值也取决于初始状态和查询含义。这里返回零,是因为维护全零数组的和;如果维护集合最小值、最大值,必须重新确定空区间语义。
8 与离散化比较
已知全部操作坐标时,离散化通常占用更少空间。无法提前知道坐标、但有明确值域边界时,动态开点可以按输入顺序处理。
两者都是节点组织方式的选择。可持久化与线段树合并也常使用显式孩子编号,但它们的节点共享和修改规则各不相同。
9 练习
- 连续查询从未修改的区间,检查
tot是否保持不变。 - 在同一个坐标反复加减,检查已有节点能否复用。
- 将 权值线段树 改为动态开点频次树,按输入顺序完成排名和第
小查询。
10 相关题解
暂无相关题解