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

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

upd on 2025/11/27: 增加基础线段树、线段树合并

ps: 线段树分裂我还没学，学完加上！

线段树

实现原理

给你一个数组，让你区间加（修改），区间求和，要求 \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);
}