学术
从树的角度理解优化算法（树化思想）
_Separation WA的一声就哭了 SU @ 2026-1-18 11:40:58

树化

如果把算法学习比作搭建一座知识体系，那么树就是其中最重要的支架之一。大量高效算法之所以能做到 $O(\log n)$ ，并不是因为技巧繁复，而是因为它们共享同一种结构性优势： 用树来组织信息，用树高来限制代价 。

当数据被存放在一棵近似平衡的树上，查找、插入、删除不过是在树上走过若干层；当区间被线段树分裂成节点块，区间查询与修改也不过访问少量层级；当我们进行二分、倍增或快速幂，本质上是在一棵隐式的决策树上向下前进。树的高度是 $\log n$ ，于是操作复杂度自然落在 $\log n$ 上。

本章将从 为什么折半会产生 $\log n$ 讲起，逐步解释堆、平衡树、线段树、树状数组以及树上倍增 / 剖分等经典结构背后的统一逻辑，帮助同学们在遇到新题时第一时间判断：

这道题能不能树化？

树高是多少？

一次操作会走几层？

只要抓住这三点， $\log n$ 不再是结论，而会变成你能亲手推导出来的直觉。

正文（硬核讲解）

从二分开始理解所有 $O(\log n)$

二分查找是最早会接触到、也最值得反复练的 $O(\log n)$ 算法。因为它把折半和树高这两个核心直觉一次性讲透： 每比较一次，就把答案所在范围缩小一半 ，所以最多比较 $\lceil \log_2 n\rceil$ 次。

当然二分查找的前提只有一个关键词： 单调性 。

如果没有 单调性 的话从数据储存的角度看，这个时候的数据是无序的，只能储存在一个线性的结构中，这个时候只能遍历整个序列一个一个对比。

for (x <- 整个序列) if (x 是目标) 得到答案

但是数据具有 单调性 （更准确地说：整体有序 / 可比较并能保持有序）的时候，就可以把 线性扫描 升级为 折半定位 。此时数据不再只能用线性结构 从头到尾比 ，而是可以建立一种 层级结构 来快速缩小范围——最典型的就是把有序序列看成一棵 隐式二叉树 ，每次比较都相当于在树上走下一层。

有单调性：每次比较都能排除一半

假设序列按从小到大排序（单调不降）：

a_1 \le a_2 \le \cdots \le a_n

要找目标值 $t$ （或找第一个满足条件的位置）。只需要维护当前可能存在答案的区间 $[l, r]$ ，每次取中点 $\text{mid}$ ：

若 $a_{mid} >= t$ ，说明答案在左半边（含 $\text{mid}$ ），令 $r = mid$
若 $a_{mid} < t$ ，说明答案只能在右半边，令 $l = mid + 1$

这样区间长度会不断减半，从 $n$ 变成 $\frac{n}{2}, \frac{n}{4}, ...$ ，最多进行 $\lceil \log_2 n\rceil$ 次比较就能定位到答案。

代码模板：边界二分（最常用，找第一个 $\ge t$ ）

int l = 1, r = n; // 目标：找到第一个 >= t 的位置
while (l < r) {
    int mid = l + (r - l) / 2;
    if (a[mid] >= t) r = mid;     // 答案在 [l, mid]
    else l = mid + 1;             // 答案在 [mid+1, r]
}
// 结束时 l == r
if (a[l] >= t) ans = l; else ans = -1;

这就是 $\text{lower_bound}$ 的核心思想。

代码模板：边界二分（最常用，找第一个 $> t$ ）

int l = 1, r = n; // 目标：找到第一个 > t 的位置
while (l < r) {
    int mid = l + (r - l) / 2;
    if (a[mid] > t) r = mid;      // 答案在 [l, mid]
    else l = mid + 1;             // 答案在 [mid+1, r]
}
// 结束时 l == r
if (a[l] > t) ans = l; else ans = -1; // 不存在则 -1

这就是 $\text{upper_bound}$ 的核心思想。

为什么可以这么做？（单调性带来的可判定方向）

关键在于：当序列有序时，比较一次 $a_{mid}$ 和 $t$ ，就能 确定答案在哪一边 ，另一边可以全部排除。

$a_{mid}$ 已经不小于 $t$ ，那么右边更大，不会更靠左 $⇒$ 去左边找 更早的满足
$a_{mid}$ 还小于 $t$ ，那么左边更小，永远达不到 $⇒$ 直接抛弃左边

这就是 单调性 的真正力量： 它让你每一步都有明确方向 。

重点：树视角：二分就是在走一棵高度为 $\log n$ 的树

把区间不断二分，等价于一棵二叉树：

根节点：整个区间 $[1, n]$
左孩子： $[1, mid]$
右孩子： $[mid + 1, n]$

每比较一次，就从父区间走到子区间（下一层）。而这棵树的高度就是 $\log n$ ，所以二分查找的复杂度自然是：

O(\log n)

从有序数组到二分答案（更广义的单调性）

顺便讲一下，虽然和本章讲的没什么太大关系。

注意：这里的 单调性 不一定来自数组排序，也可以来自一个判定函数：

当 $mid$ 小时不满足
当 $mid$ 大到某个点后永远满足

也就是 $\text{check(mid)}$ 形如：

$$\underbrace{false,\ false,\ \dots}_{\text{不行}} \underbrace{true,\ true,\ \dots}_{\text{可行}} $$

此时二分的不是数组下标，而是 答案本身 。

$\text{check(x)}$ 的单调性是什么？（ $x$ 就是 $mid$ ，需要二分的东西）

可以把 $\text{check(x)}$ 理解成一句话：

如果答案允许我用 $x$ 这么多资源（时间 / 次数 / 容量 / 距离 / 预算），我能否完成任务？

只要这个问题具有 资源越多越容易成功 的性质，就会单调：

$x$ 越大越容易成功 $⇒$ $\text{check(x)}$ 从 false 变 true 且不回头
这种题就适合二分答案

常见关键词（看到就想二分答案）：

最小时间 / 最小容量 / 最小最大值 / 最小距离 / 最小操作次数

是否能在 $X$ 内完成？

能否把代价控制在 $X$ 以内？

二分答案的流程

需要先确定答案范围 $[L, R]$ ：

$L$ ：一定不行的下界（或可能行）
$R$ ：一定行的上界（关键：要能保证存在可行）

然后重复：

取 $mid$
如果 $check(mid)$ 为真：说明答案可以更小 $⇒$ $r = mid$
否则：答案必须更大 $⇒$ $l = mid + 1$

最终得到最小可行解。

模版

LL l = L, r = R; // 目标：找到最小的 x，使得 check(x) == true
while (l < r) {
    LL mid = l + (r - l) / 2;
    if (check(mid)) r = mid;     // mid 可行，往更小找
    else l = mid + 1;            // mid 不可行，只能变大
}
// 结束时 l == r
ans = l; // 最小可行值

注意：这里必须保证 $R$ 是可行的 ，否则最后的 $ans$ 没意义。

难点

二分答案的难点通常不在二分，而在 $\text{check(x)}$ 的实现。

$\text{check(x)}$ 常见写法有几类：

贪心：给定上限 $x$ ，按最优策略模拟，看能否成功。

前缀和 / 差分：判断某些约束是否能满足。

DP 简化：只判断 是否存在方案 ，不求最优值。

图 / 并查集：给定阈值 $x$ ，只允许边权 $\le x$ ，看是否连通等。

可以把二分答案理解为： 外层二分缩小答案范围，内层 $\text{check}$ 验证给你这个答案，行不行。

用分治实现二分（直观树化）

用分治 / 递归来写二分 ，对 二分 $=$ 走一棵树 会更直观：每次递归把区间分成左右两半，实际上就在 递归树 里往下一层走。

不过要注意一点：二分查找严格来说不是 同时分治两边 ，而是 分裂后只进入其中一边 （所以递归树并不会完整展开成两棵子树，而是沿着一条路径下钻）。

但是这也正好解释了为什么是 $O(\log n)$ ： 只走树高，不遍历整棵树 。

模版

int lb_dc(int l, int r, int t) { // 返回第一个 >= t 的下标，不存在返回 -1
    if (l == r) return (a[l] >= t ? l : -1);
    int mid = l + (r - l) / 2;
    if (a[mid] >= t) return lb_dc(l, mid, t);     // 去左半边
    else return lb_dc(mid + 1, r, t);             // 去右半边
}

int ub_dc(int l, int r, int t) { // 返回第一个 > t 的下标，不存在返回 -1
    if (l == r) return (a[l] > t ? l : -1);
    int mid = l + (r - l) / 2;
    if (a[mid] > t) return ub_dc(l, mid, t);      // 去左半边
    else return ub_dc(mid + 1, r, t);             // 去右半边
}

二分具像化展示

画的图实在太难看，所以还是写个程序打印出来吧，请读者感性理解，实在无法感性的话再找我私聊。

关注公众号 就可以加 V 。

#include <bits/stdc++.h>
using namespace std;
struct node {
    int l, r, mid;   // 区间 [l, r] 的 mid
    int lc, rc;      // 左右孩子（-1 表示无）
};
struct Step {
    int id;
    char go; // 'L' / 'R' / '-'(leaf)
};
vector<node> tr;
vector<int> a;          // 1-indexed，有序数组
vector<Step> steps;     // 只记录“实际走过的那条链”
int build(int l, int r) {
    int id = (int)tr.size();
    tr.push_back({l, r, l + (r - l) / 2, -1, -1});
    if (l < r) {
        int mid = tr[id].mid;
        tr[id].lc = build(l, mid);
        tr[id].rc = build(mid + 1, r);
    }
    return id;
}
// strict=false => 找第一个 >= t
// strict=true  => 找第一个 >  t
void trace(int id, int t, bool strict) {
    int l = tr[id].l, r = tr[id].r, mid = tr[id].mid;
    if (l == r) {
        steps.push_back({id, '-'});
        return;
    }
    bool goLeft = strict ? (a[mid] > t) : (a[mid] >= t);
    steps.push_back({id, goLeft ? 'L' : 'R'});
    trace(goLeft ? tr[id].lc : tr[id].rc, t, strict);
}
void print_full_tree(int id, const string& prefix, bool isLeft,
                     const vector<char>& vis, int t, bool strict) {
    const auto &nd = tr[id];
    bool marked = (vis[id] != 0);
    // 画分支
    if (!prefix.empty()) {
        cout << prefix << (isLeft ? "├─L-> " : "└─R-> ");
    }
    // 节点信息
    cout << (marked ? "* " : "  ")
         << "[" << nd.l << "," << nd.r << "] mid=" << nd.mid;
    // 顺便把 mid 的值也显示出来（叶子也显示）
    if (nd.mid >= 1 && nd.mid < (int)a.size()) {
        cout << "  a[mid]=" << a[nd.mid];
    }
    // 如果这个节点在路径上且不是叶子，显示这一步的判断
    if (marked && nd.l != nd.r) {
        bool goLeft = strict ? (a[nd.mid] > t) : (a[nd.mid] >= t);
        cout << "   ("
             << (strict ? "a[mid] > t" : "a[mid] >= t")
             << " ? go L : go R) => go " << (goLeft ? "L" : "R");
    }
    cout << "\n";
    if (nd.lc != -1) {
        string nextPref = prefix + (prefix.empty() ? "" : (isLeft ? "│     " : "      "));
        // 根节点特殊处理：prefix 为空时，左右子树都作为“根的孩子”打印
        if (prefix.empty()) {
            print_full_tree(nd.lc, "", true, vis, t, strict);
            print_full_tree(nd.rc, "", false, vis, t, strict);
        } else {
            print_full_tree(nd.lc, nextPref, true, vis, t, strict);
            print_full_tree(nd.rc, nextPref, false, vis, t, strict);
        }
    }
}
// 只打印“被访问的那条链”，更像递归调用栈
void print_only_path(int t, bool strict) {
    cout << "Visited path (" << (strict ? "first > t" : "first >= t") << "):\n";
    for (int i = 0; i < (int)steps.size(); i++) {
        int id = steps[i].id;
        const auto &nd = tr[id];
        string ind(i * 2, ' ');
        cout << ind << "* [" << nd.l << "," << nd.r << "] mid=" << nd.mid
             << " a[mid]=" << a[nd.mid];

        if (steps[i].go == '-') {
            cout << "  (leaf)\n";
        } else {
            bool goLeft = (steps[i].go == 'L');
            cout << "  -> " << (goLeft ? "L" : "R") << "\n";
        }
    }
    int leaf = steps.back().id;
    cout << "Answer index = " << tr[leaf].l << "\n\n";
}
int main() {
    int n = 16;
    a.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) a[i] = i; // 示例：a[i]=i（单调）
    tr.clear();
    int root = build(1, n);
    int t = 11;
    // ====== 1) 找第一个 >= t ======
    steps.clear();
    trace(root, t, false);
    vector<char> vis(tr.size(), 0);
    for (auto &st : steps) vis[st.id] = 1;
    cout << "=== Full tree (marked nodes are visited) : first >= t, t=" << t << " ===\n";
    // 根节点单独打印得更像“图”
    cout << "* [1," << n << "] mid=" << tr[root].mid << "  a[mid]=" << a[tr[root].mid]
         << "  (root)\n";
    print_full_tree(tr[root].lc, "", true, vis, t, false);
    print_full_tree(tr[root].rc, "", false, vis, t, false);
    cout << "\n";
    print_only_path(t, false);
    // ====== 2) 找第一个 > t ======
    steps.clear();
    trace(root, t, true);
    fill(vis.begin(), vis.end(), 0);
    for (auto &st : steps) vis[st.id] = 1;
    cout << "=== Full tree (marked nodes are visited) : first > t, t=" << t << " ===\n";
    cout << "* [1," << n << "] mid=" << tr[root].mid << "  a[mid]=" << a[tr[root].mid]
         << "  (root)\n";
    print_full_tree(tr[root].lc, "", true, vis, t, true);
    print_full_tree(tr[root].rc, "", false, vis, t, true);
    cout << "\n";
    print_only_path(t, true);
    return 0;
}

* 代表的是到达的子树。

=== Full tree (marked nodes are visited) : first >= t, t=11 ===
* [1,16] mid=8  a[mid]=8  (root)
  [1,8] mid=4  a[mid]=4
  [1,4] mid=2  a[mid]=2
  [1,2] mid=1  a[mid]=1
  [1,1] mid=1  a[mid]=1
  [2,2] mid=2  a[mid]=2
  [3,4] mid=3  a[mid]=3
  [3,3] mid=3  a[mid]=3
  [4,4] mid=4  a[mid]=4
  [5,8] mid=6  a[mid]=6
  [5,6] mid=5  a[mid]=5
  [5,5] mid=5  a[mid]=5
  [6,6] mid=6  a[mid]=6
  [7,8] mid=7  a[mid]=7
  [7,7] mid=7  a[mid]=7
  [8,8] mid=8  a[mid]=8
* [9,16] mid=12  a[mid]=12   (a[mid] >= t ? go L : go R) => go L
* [9,12] mid=10  a[mid]=10   (a[mid] >= t ? go L : go R) => go R
  [9,10] mid=9  a[mid]=9
  [9,9] mid=9  a[mid]=9
  [10,10] mid=10  a[mid]=10
* [11,12] mid=11  a[mid]=11   (a[mid] >= t ? go L : go R) => go L
* [11,11] mid=11  a[mid]=11
  [12,12] mid=12  a[mid]=12
  [13,16] mid=14  a[mid]=14
  [13,14] mid=13  a[mid]=13
  [13,13] mid=13  a[mid]=13
  [14,14] mid=14  a[mid]=14
  [15,16] mid=15  a[mid]=15
  [15,15] mid=15  a[mid]=15
  [16,16] mid=16  a[mid]=16

Visited path (first >= t):
* [1,16] mid=8 a[mid]=8  -> R
  * [9,16] mid=12 a[mid]=12  -> L
    * [9,12] mid=10 a[mid]=10  -> R
      * [11,12] mid=11 a[mid]=11  -> L
        * [11,11] mid=11 a[mid]=11  (leaf)
Answer index = 11

=== Full tree (marked nodes are visited) : first > t, t=11 ===
* [1,16] mid=8  a[mid]=8  (root)
  [1,8] mid=4  a[mid]=4
  [1,4] mid=2  a[mid]=2
  [1,2] mid=1  a[mid]=1
  [1,1] mid=1  a[mid]=1
  [2,2] mid=2  a[mid]=2
  [3,4] mid=3  a[mid]=3
  [3,3] mid=3  a[mid]=3
  [4,4] mid=4  a[mid]=4
  [5,8] mid=6  a[mid]=6
  [5,6] mid=5  a[mid]=5
  [5,5] mid=5  a[mid]=5
  [6,6] mid=6  a[mid]=6
  [7,8] mid=7  a[mid]=7
  [7,7] mid=7  a[mid]=7
  [8,8] mid=8  a[mid]=8
* [9,16] mid=12  a[mid]=12   (a[mid] > t ? go L : go R) => go L
* [9,12] mid=10  a[mid]=10   (a[mid] > t ? go L : go R) => go R
  [9,10] mid=9  a[mid]=9
  [9,9] mid=9  a[mid]=9
  [10,10] mid=10  a[mid]=10
* [11,12] mid=11  a[mid]=11   (a[mid] > t ? go L : go R) => go R
  [11,11] mid=11  a[mid]=11
* [12,12] mid=12  a[mid]=12
  [13,16] mid=14  a[mid]=14
  [13,14] mid=13  a[mid]=13
  [13,13] mid=13  a[mid]=13
  [14,14] mid=14  a[mid]=14
  [15,16] mid=15  a[mid]=15
  [15,15] mid=15  a[mid]=15
  [16,16] mid=16  a[mid]=16

Visited path (first > t):
* [1,16] mid=8 a[mid]=8  -> R
  * [9,16] mid=12 a[mid]=12  -> L
    * [9,12] mid=10 a[mid]=10  -> R
      * [11,12] mid=11 a[mid]=11  -> R
        * [12,12] mid=12 a[mid]=12  (leaf)
Answer index = 12

线段树（二分之后最自然的树化）

线段树 就是把二分里那棵 隐式区间二叉树显式建出来 ，然后在每个节点存一段区间的信息（ $sum/max/min…$ ），从 只会找位置 升级成 能维护、能查询 。

线段树因为需要储存信息，为了方便用数组储存最方便。因为要储存一个区间 $[l, r]$ 的东西，不妨建立结构体：

struct node
{
    int l, r, mid;  // 这个节点管的区间 [l, r]，mid = (l + r) / 2
    LL Sum; // 区间的和（比较经典，也可以维护其他的，比如最大值，最小值...）
}tr[N << 2];

线段树的树化本质： 把区间一分为二 （和二分一模一样），只不过把每个区间都保存成一个节点储存在 $\text{tr}$ 中。

建树 build：递归分裂区间（就是把树长出来）

建树的逻辑非常像分治：

如果 $l=r$ ：这是叶子， $sum = a_l$ 。
否则分裂成左右子区间，先建左右，再合并。

// 左右儿子下标：p 的左儿子是 2 * p，右儿子是 2 * p + 1
#define ls(x) ((x) << 1)
#define rs(x) (((x) << 1) | 1)
// pull：把左右子区间的信息 向上合并 到父区间
inline void pull(int p) {tr[p].sum = tr[ls(p)].sum + tr[rs(p)].sum;}
// build：建树（把数组 a[1..n] 初始化到线段树里）
// p：当前线段树节点编号
// l, r：当前节点管的区间范围
void build(int p, int l, int r) {
    tr[p].l = l; tr[p].r = r;
    tr[p].mid = l + (r - l) / 2;
    // 叶子节点：区间长度为 1，对应数组中的一个元素
    if (l == r) {
        tr[p].Sum = a[l];
        return;
    }
    // 递归建左右子树
    int m = tr[p].mid;
    build(ls(p), l, m);
    build(rs(p), m + 1, r);
    // 向上合并（回溯时合并子树信息）
    pull(p);    
}

单点修改 update：像二分一样只走一条链

把位置 $idx$ 的值改成 $val$ ：

如果当前节点是叶子：直接改 $sum$ 。
否则看 $idx$ 在左区间还是右区间，只递归进入一边 。
回溯时更新父节点 $sum$ 。

这一步和二分查找完全同构：每层只选一边 $⇒$ 走树高 $⇒$ $O(\log n)$ 。

// update：单点修改，把 a[idx] 改成 val
// p：当前节点编号
// idx：要修改的位置
// val：新值
void update(int p, int idx, LL val) {
    int l = tr[p].l, r = tr[p].r;
    // 找到叶子（对应 idx 的那个点）
    if (l == r) {
        tr[p].sum = val;
        return;
    }
    // 根据 idx 落在哪个半区，递归进入左子树或右子树
    int m = tr[p].mid;
    if (idx <= m) update(ls(p), idx, val);
    else update(rs(p), idx, val);
    // 修改完子树后，回溯更新当前节点的区间信息
    pull(p);
}

区间查询 query：把查询区间拆成少量节点块

查询区间 $[L,R]$ 的和：

若当前节点区间 $[l,r]$ 完全在 $[L,R]$ 内：直接返回 $sum$ 。
若完全不相交：返回 $0$ 。
否则：分裂到左右孩子，把结果加起来。

还是 $O(\log n)$

因为 $[L,R]$ 在每一层最多切到常数个节点块，整体访问节点数是对数级（常见说法：不超过 $4\log n$ 量级）。

// query：查询区间 [L, R] 的区间和
// p：当前节点编号
// L, R：查询目标区间
LL query(int p, int L, int R) {
    int l = tr[p].l, r = tr[p].r;
    // 当前节点区间被查询区间完全覆盖：直接返回该节点维护的信息
    if (L <= l && r <= R) return tr[p].Sum;
    // 否则，把查询区间拆到左右子区间去
    int m = tr[p].mid;
    LL Res = 0;
    // 左子区间有交集
    if (L <= m) Res += query(ls(p), L, R);
    // 右子区间有交集
    if (R >  m) Res += query(rs(p), L, R);
    return Res;
}

完整代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
struct node
{
    int l, r, mid;  // 这个节点管的区间 [l, r]，mid = (l + r) / 2
    LL Sum; // 区间的和（比较经典，也可以维护其他的，比如最大值，最小值...）
}tr[N << 2];
int n, q, a[N];
// 左右儿子下标：p 的左儿子是 2 * p，右儿子是 2 * p + 1
#define ls(x) ((x) << 1)
#define rs(x) (((x) << 1) | 1)
// pull：把左右子区间的信息 向上合并 到父区间
inline void pull(int p) {tr[p].Sum = tr[ls(p)].Sum + tr[rs(p)].Sum;}
// build：建树（把数组 a[1..n] 初始化到线段树里）
// p：当前线段树节点编号
// l, r：当前节点管的区间范围
void build(int p, int l, int r) {
    tr[p].l = l; tr[p].r = r;
    tr[p].mid = l + (r - l) / 2;
    // 叶子节点：区间长度为 1，对应数组中的一个元素
    if (l == r) {
        tr[p].Sum = a[l];
        return;
    }
    // 递归建左右子树
    int m = tr[p].mid;
    build(ls(p), l, m);
    build(rs(p), m + 1, r);
    // 向上合并（回溯时合并子树信息）
    pull(p);    
}
// update：单点修改，把 a[idx] 改成 val
// p：当前节点编号
// idx：要修改的位置
// val：新值
void update(int p, int idx, LL val) {
    int l = tr[p].l, r = tr[p].r;
    // 找到叶子（对应 idx 的那个点）
    if (l == r) {
        tr[p].Sum = val;
        return;
    }
    // 根据 idx 落在哪个半区，递归进入左子树或右子树
    int m = tr[p].mid;
    if (idx <= m) update(ls(p), idx, val);
    else update(rs(p), idx, val);
    // 修改完子树后，回溯更新当前节点的区间信息
    pull(p);
}
// query：查询区间 [L, R] 的区间和
// p：当前节点编号
// L, R：查询目标区间
LL query(int p, int L, int R) {
    int l = tr[p].l, r = tr[p].r;
    // 当前节点区间被查询区间完全覆盖：直接返回该节点维护的信息
    if (L <= l && r <= R) return tr[p].Sum;
    // 否则，把查询区间拆到左右子区间去
    int m = tr[p].mid;
    LL Res = 0;
    // 左子区间有交集
    if (L <= m) Res += query(ls(p), L, R);
    // 右子区间有交集
    if (R >  m) Res += query(rs(p), L, R);
    return Res;
}
inline void solve() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    // 建树：O(n)
    build(1, 1, n);
    // 1 x v  -> 把 a[x] 改成 v
    // 2 l r  -> 查询 [l, r] 区间和
    while (q--) {
        int op; cin >> op;
        if (op == 1) {
            int x; LL v;
            cin >> x >> v;
            update(1, x, v); // 单点修改：O(log n)
        } else {
            int l, r;
            cin >> l >> r;
            cout << query(1, l, r) << "\n"; // 区间查询：O(log n)
        }
    }
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

一车 $O(\log n)$

并查集 DSU（路径压缩：把树压扁）

二分对象：集合代表节点的父指针链（森林结构）。
分裂规则：路径压缩把链压到根上，降低高度。
像二分的点：虽然不是严格的 $\log n$ ，但本质依赖 树高变小 来加速（均摊接近常数，常用直觉是 树越矮越快 ）。

典型题：连通性、 $\text{Kruskal}$ 、动态合并。

倍增 / Binary Lifting（树上跳跃：按 $2^k$ 分层）

二分对象：步数 / 距离（按二进制拆分）。
分裂规则：把 $k$ 表示成若干个 $2^i$ 之和。
像二分的点：每次用一个 $2^i$ 的跳跃砍掉一部分距离，最多用到 $\log k$ 个二进制位。

典型题： $\text{LCA}$ 、 $\text{k-th ancestor}$ 、树上跳点、倍增 DP。

稀疏表 Sparse Table（RMQ：倍增层级）

二分对象：区间长度（按 $2^k$ 分层）。
分裂规则：把任意区间拆成两个长度为 $2^k$ 的块（重叠覆盖）。
像二分的点：查询时只用到 $\log$ 层里的一个 $k=\lfloor \log_2 len \rfloor$ （常数次合并），预处理是 $O(n\log n)$ 。

典型题：静态区间最值 / 最小值（RMQ）。

树状数组 Fenwick / BIT（线段树的隐式压缩版）

二分对象：前缀区间（用 $\text{lowbit}$ 分块）。
分裂规则：用二进制最低位把前缀拆成若干块。
像二分的点：每次 $i -= \text{lowbit(i)}$ 或 $i += \text{lowbit(i)}$ ，相当于沿着一棵隐式树 向上 / 向下跳 ，跳次数是 $O(\log n)$ 。

它不是显式 $\text{mid}$ ，但本质仍是 层级结构 + 走对数层 。

平衡二叉搜索树 BST（二分值域 / 排序后的相对位置）

二分对象：按 $\text{key}$ 的 有序集合 。
分裂规则：小的去左子树，大的去右子树。
像二分的点：查找 / 插入 / 删除都像二分一样一路比较一路下走（树高 $\log n$ ）。

常见： $\text{set / map}$ （红黑树）、 $\text{Treap}$ 、 $\text{AVL}$ 、 $\text{Splay}$ 。

这是 把有序数组的二分 推广成 动态维护的二分 。

堆 Heap（完全二叉树：局部有序的二分层级）

二分对象：层级结构（不是全局有序）。
像二分的点： $\text{push / pop}$ 只做 上浮 / 下沉 ，走的就是树高 $\log n$ 。

它的树化不靠单调数组，而靠 完全二叉树高度低 。

二进制 Trie / 01-Trie（二分二进制前缀）

二分对象：二进制位（ $\text{0/1}$ ）。
分裂规则：每一层按当前 $\text{bit}$ 分到 $0$ 分支或 $1$ 分支。
像二分的点：每层做一次 去左还是去右 的决定，深度固定（例如 $\text{31/63}$ 层），复杂度类似 $O(\log V)$ 。

典型题：最大异或、按位统计、K 小 xor 等。

跳表 Skip List（多层二分索引）

二分对象：有序链表的索引层。
像二分的点：从高层往下走，像在多层索引树里逐层逼近（期望 $O(\log n)$ ）。

分裂合并 Treap / Rope（维护序列：按位置二分）

二分对象：序列的位置/排名（隐式 key）。
分裂规则：按 $\text{size}$ 把树 $\text{split}$ 成两棵，再 $\text{merge}$ 回去。
像二分的点： $\text{split / merge}$ 本质就是在平衡树上按排名走路径，树高 $\log n$ 。

典型题：区间翻转、区间插入删除、序列维护。

可回滚并查集 + 线段树分治（离线动态连通）

二分对象：时间区间（操作序列的区间）。
分裂规则：把时间轴按 $\text{mid}$ 分裂成左右两段（线段树分治）。
像二分的点：每条边被分配到 $O(\log q)$ 个时间节点上，递归遍历像 走时间区间树 。

典型题：动态加边删边问连通、离线维护。

更进阶的二分式树化

这些也是 层层分裂 + 树高对数 ，但比前面更偏技巧：

可持久化线段树（主席树）：每次修改复制一条根到叶路径（仍像二分走链）。
动态开点线段树：值域巨大但点很少，仍按 $\text{mid}$ 分裂。
点分治（重心分解）：把树按重心层层分裂，层数 $\log n$ 。
树链剖分 HLD：把路径分成若干段，再用线段树维护（常见 $O(\log^2 n)$ ）。

目前还没有评论...

从树的角度理解优化算法（树化思想）

树化