线段树——最好用的数据结构的学习笔记

HydrogenOxygen · 2025-11-25 15:22:48 · 算法·理论

更新日志

write on 2025/11/25: 动态开点线段树与主席树的学习笔记。\ upd on 2025/11/27: 增加基础线段树、线段树合并。\ upd on 2026/01/15: 增加线段树分治并修了一些已知的锅。\ upd on 2026/04/16: 我又回来了，这次看到一个好题，必须加上！另外补充动态 DP。\ upd on 2026/04/24: 我又回来了，这次更线段树分裂！要不要我更可持久化并查集？要；不要。

线段树

实现原理

给你一个数组，让你区间加（修改），区间求和，要求 \le\mathcal O((n+q)\log n) 实现，可以怎么做？

树状数组线段树。

考虑每个区间分成 \log n 个小区间之和。

可以考虑将最大的大区间一分为二，小区间再一分为二，再分，直到一个节点为止。如字符画。

| 1 | 2 | 3 | 4 | 5 |
|-------------------|       -->一层 segment tree 总体管辖整个区间
|-----------|-------|       -->分成小线段管辖
|-------|---|---|---|       -->再分，线段内存储的是这些数的<询问类型>
|---|---|                   -->分到一个就不往下分了

先写出建树：

#define ls (p<<1) // 写成 1<<p 痛失 3 罚时
#define rs (p<<1|1)
const int maxn=2e5+5;
long long segtree[maxn<<2]/*注意是 4 倍空间*/,a[maxn],lazy[maxn],n,q;
void pushup(long long l,long long r,long long p){
    segtree[p]=segtree[ls]+segtree[rs];
}
void build(long long l,long long r,long long p){
    if(l==r){
        segtree[p]=a[l];
        return;
    }
    long long mid=l+r>>1;
    build(l,mid,ls);
    build(mid+1,r,rs);
    pushup(l,r,p);
}