算法知识图谱总览 / 线段树族 / 动态开点线段树

动态开点线段树

P1advancedstandardG-A-6
← 上一个 / 组内seg-lazy 组内第 3 / 4返回组索引 全局返回总览 下一个 / 组内seg-merge

What · 是什么

按需创建节点，支持大值域离散化无需预先开空间

不再用 2p/2p+1 固定编号，而是用 ls[p]/rs[p] 显式记录子节点编号，仅在真正访问某子区间时才新建节点，使大值域(如 1e18)无需离散化即可直接建树。

Why · 为什么

直觉 · Intuition

值域 1e18 时堆式 4N 数组开不下；但若实际只改/查了 Q 个点，真正用到的节点不过 O(Q log V) 个——那干脆用多少开多少。

原理 · Principle

全局维护节点池 ls/rs/sum 数组与计数器 tot，new_node() 每次追加一个新节点。update/query 递归时若 p==0 表示该子区间从未被创建，按需求新建(单点)或直接返回空值(查询)。区间修改仍可配懒标记，但 pushdown 时若子节点不存在要先 new_node。

历史 · History

动态开点线段树是显式节点结构（平衡树/主席树）思想在线段树上的应用，OI Wiki ds/seg 章节「动态开点线段树」小节介绍，广泛用于权值线段树与大值域问题。

How · 实现

伪代码

update(x,f,s,t,p): 若 !p 则 p=new_node(); sum[p]+=f; 若 s==t 返回; 按 m 递归 ls/rs
query(l,r,s,t,p): 若 !p 返回 0; 若 ⊆ 返回 sum[p]; 否则递归

Python 实现

import sys

# 动态开点线段树: 大值域(如 1e18)离散化或直接按需建点
MAXV = 1 << 60
tot = 0
ls = [0]
rs = [0]
sm = [0]


def new_node():
    global tot
    tot += 1
    ls.append(0)
    rs.append(0)
    sm.append(0)
    return tot


def update(x, f, s, t, p):
    # 单点修改: 位置 x 加 f
    if not p:
        p = new_node()
    sm[p] += f
    if s == t:
        return p
    m = s + ((t - s) >> 1)
    if x <= m:
        ls[p] = update(x, f, s, m, ls[p])
    else:
        rs[p] = update(x, f, m + 1, t, rs[p])
    return p


def query(l, r, s, t, p):
    # 区间查询 [l,r] 的和
    if not p or l > t or r < s:
        return 0
    if l <= s and t <= r:
        return sm[p]
    m = s + ((t - s) >> 1)
    res = 0
    if l <= m:
        res += query(l, r, s, m, ls[p])
    if r > m:
        res += query(l, r, m + 1, t, rs[p])
    return res


if __name__ == "__main__":
    sys.setrecursionlimit(1 << 20)
    root = new_node()
    root = update(3, 7, 1, MAXV, root)
    root = update(100, 4, 1, MAXV, root)
    print(query(1, 10, 1, MAXV, root))   # 7
    print(query(1, 200, 1, MAXV, root))  # 11
PyPy 提示节点池用并行列表 ls/rs/sum + 计数器 tot，避免对象数组开销；递归深度需 setrecursionlimit。
时间复杂度O((N+Q)log V) — V 为值域；只创建访问过的节点
空间复杂度O((N+Q)log V) — 节点池按需增长
注意 · 局限Python 全局可变列表(append)做节点池可行但常数大；值域过大应先离散化把 V 压到 n 量级再开 4N 静态数组更快；区间修改可用标记永久化免去 pushdown 时的 new_node 开销。

易错点

例题

OJ题号难度考点链接
LuoguP138255线段树1.5 动态开点模板：区间加+区间和，大值域直接开点https://www.luogu.com.cn/problem/P13825
步骤迷你图（节点 = 算法步骤 · 边 = 流程 · 绿色 = 起始步骤）
上游 · 本知识点依赖（前置/变体/组合/共现）
线段树基础变体懒标记线段树前置依赖
下游 · 依赖本知识点
线段树合并与分裂前置依赖可持久化线段树(主席树)前置依赖

信源

✓ = 已核验 · △ = 未核验