Accepted · 进阶数据结构/ 7.1 → 7.2

第七部分 · PART 7

进阶数据结构

铜牌知识体系的最后一块拼图——树状数组与线段树。它们都用来高效处理「动态修改 + 区间查询」，是前缀和扛不住「边改边查」时的升级武器。

从树状数组（前缀和的升级版，求区间和、逆序对，代码极短）起步，到线段树入门（更通用的区间数据结构）。本节末尾也是整套铜牌正课的收尾——七大部分到此走完。

第七部分 · 7.1

7.1 树状数组（Binary Indexed Tree / Fenwick Tree）

教教练衔接coach

进入 第七部分：进阶数据结构——铜牌知识体系的最后一块拼图！从树状数组开始。它是前缀和的"升级版"——前缀和只能处理静态数组（不能修改），树状数组能在支持动态修改的同时高效查询区间和。

先抓住它解决的核心问题：

树状数组 = 一种支持"单点修改 + 区间查询"都是 O(log n) 的数据结构。
回忆 1.3：前缀和能 O(1) 查区间和，但数组一旦修改就要重新算前缀和（O(n)）。如果既要频繁修改、又要频繁查询区间和，前缀和就不够了——这正是树状数组的用武之地。

一、为什么需要树状数组（动机）

回顾你学过的工具处理"区间和"问题：

方法	单点修改	区间查询	适用
普通数组	O(1)	O(n)（暴力累加）	修改多、查询少
前缀和（1.3）	O(n)（要重算）	O(1)	查询多、不修改
树状数组	O(log n)	O(log n)	既改又查

关键场景：当问题是"多次单点修改 + 多次区间求和"交替进行时，前缀和（改一次要 O(n) 重算）和普通数组（查一次 O(n)）都不够。树状数组让两个操作都是 O(log n)，完美平衡。

还记得 1.3 最后说的吗——"既要改又要查，超出前缀和/差分能力，需要树状数组或线段树"。现在就是补上这块。

二、树状数组的核心思想（直观理解）

树状数组的巧妙之处在于用一个数组 tree[]，每个位置管理一段区间的和，通过二进制的特性高效地修改和查询。

核心概念 lowbit：lowbit(x) = x 的二进制中最低位的 1 所代表的值。

solution.cpp

int lowbit(int x) {
    return x & (-x);     // 取最低位的1
}

举例：lowbit(6)：6 = 110₂，最低位的 1 在第 1 位（值为 2），所以 lowbit(6) = 2。lowbit(8)：8 = 1000₂，最低位 1 在第 3 位（值 8），lowbit(8) = 8。

x & (-x) 为什么能取最低位 1：负数用补码表示，-x 是 x 取反加一，x & (-x) 恰好留下最低位的 1。这是个位运算技巧，记住 lowbit(x) = x & (-x) 即可，原理可以慢慢理解。

树状数组的结构：tree[i] 存储的是以 i 结尾、长度为 lowbit(i) 的区间和，即 tree[i] = a[i-lowbit(i)+1] + ... + a[i]。通过 lowbit 的跳转，能用 O(log n) 个 tree 值拼出任意前缀和。

树状数组的原理（为什么 lowbit 能让修改和查询都 O(log n)）比较抽象，初学先记住模板会用即可——它的两个操作（更新、查询）都很短，理解"通过 lowbit 跳转，每次跳过一段"这个直觉就够，深入原理可以后续慢慢消化。

三、树状数组模板（背下来）

树状数组就两个核心操作，代码极短：

solution.cpp

const int N = 1e5 + 5;
int tree[N];          // 树状数组
int n;                // 数组大小

int lowbit(int x) { return x & (-x); }

// 操作1：单点修改——给位置 i 加上 v
void update(int i, int v) {
    for (; i <= n; i += lowbit(i))   // 向上跳，更新所有管辖 i 的区间
        tree[i] += v;
}

// 操作2：查询前缀和——求 a[1] + a[2] + ... + a[i]
int query(int i) {
    int sum = 0;
    for (; i > 0; i -= lowbit(i))    // 向下跳，累加各段
        sum += tree[i];
    return sum;
}

// 区间查询 [l, r] = 前缀和相减（接 1.3 思想）
int queryRange(int l, int r) {
    return query(r) - query(l - 1);
}

关键点拆解：

update(i, v)：在位置 i 加 v。i += lowbit(i) 向上跳，更新所有包含位置 i 的区间（O(log n) 个）。
query(i)：求前缀和 a[1..i]。i -= lowbit(i) 向下跳，把覆盖 [1, i] 的若干段加起来（O(log n) 段）。
区间和：query(r) - query(l-1)，和前缀和一样的思想（接 1.3）。
两个操作都是 O(log n)：因为 lowbit 跳转每次至少去掉一个二进制位，最多跳 log n 次。

树状数组模板就这几行，必须背熟。update（i 向上跳 += lowbit）和 query（i 向下跳 -= lowbit）是核心，加上 lowbit(x) = x&(-x)。记住"update 往上加、query 往下减"。

四、树状数组的初始化与使用

solution.cpp

int main() {
    cin >> n;
    // 初始化：把每个初始值用 update 加进去
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        update(i, x);      // 逐个加入（O(n log n)）
    }

    // 单点修改：把位置 3 增加 5
    update(3, 5);

    // 区间查询：求 [2, 5] 的和
    cout << queryRange(2, 5) << "\n";

    // 单点修改注意：如果是"把位置 i 改成 x"（而非"加 v"）
    // 要先减去旧值再加新值：update(i, x - 旧值)
    return 0;
}

一个重要细节：

update(i, v) 是"位置 i 增加 v"，不是"设为 v"。
如果要"把位置 i 设为 x"，需要 update(i, x - a[i])（先减旧值再加新值），并更新记录的 a[i]。

五、树状数组的典型应用

应用 1：动态区间和（基本用途）

"多次单点修改 + 多次查询区间和"——直接套模板。这是树状数组最基本的用途。

应用 2：求逆序对（经典应用）

还记得 1.6 用归并排序求逆序对吗？树状数组也能求逆序对，而且更通用：

思路：从左到右遍历数组，对每个数 a[i]，查询前面有多少个数比它大（这些都和 a[i] 构成逆序对），然后把 a[i] 加入树状数组。

solution.cpp

// 求逆序对（值域较小或离散化后）
long long countInversions(vector<int>& a) {
    long long cnt = 0;
    for (int i = 0; i < a.size(); i++) {
        // 查询 [a[i]+1, 最大值] 有多少个数（比 a[i] 大的）
        cnt += query(maxVal) - query(a[i]);
        update(a[i], 1);     // 把 a[i] 计入（位置是值，值是出现次数）
    }
    return cnt;
}

树状数组求逆序对的思路：用值当下标，统计每个值出现的次数；遍历时查"比当前大的数有几个"。值域大时要先离散化（接 1.1 的去重，把大值映射到小范围）。这是树状数组的经典应用，比归并排序更灵活。

应用 3：单点修改 + 区间查询的各种变体

统计某区间内满足条件的元素个数（动态）。
配合离散化处理值域大的问题。

六、树状数组 vs 线段树（预告）

树状数组和线段树（7.2，下一节）都能处理"修改 + 查询"，区别：

	树状数组	线段树
代码	极短（几行）	较长
功能	单点修改+区间和（有限）	更强大（区间修改、区间最值等）
常数	小、快	稍大

树状数组代码短、常数小，但功能有限（主要是单点修改+区间求和）；线段树功能更强（能区间修改、求区间最值等），但代码长。能用树状数组解决的优先用它（好写），需要更复杂操作（区间修改、区间最值）才上线段树。

七、树状数组解题思维

识别：单点修改 + 区间求和交替进行（前缀和不够用，因为要改）→ 树状数组。也用于求逆序对。
套模板：lowbit + update（往上加）+ query（往下减）。
初始化：逐个 update 加入初始值。
注意：update 是"加 v"不是"设为 v"；值域大要离散化。

八、本节速记卡

树状数组：支持单点修改 O(log n) + 区间求和 O(log n)，前缀和的"动态版"。
核心 lowbit：lowbit(x) = x & (-x)（最低位的1）。
模板（背熟）：
update(i, v)：for(; i<=n; i+=lowbit(i)) tree[i]+=v;（往上加）
query(i)：for(; i>0; i-=lowbit(i)) sum+=tree[i];（往下减，求前缀和）
区间和：query(r) - query(l-1)
记忆：update 往上跳加、query 往下跳减。
细节：update 是"增加 v"，设为 x 要 update(i, x-旧值)。
应用：动态区间和、求逆序对（值当下标，查比当前大的个数，值域大先离散化）。
vs 线段树：树状数组短小快但功能有限，复杂操作用线段树。
识别：单点改+区间和交替 / 求逆序对。

树状数组是性价比很高的数据结构——代码极短（几行）、效率高，专治"动态区间和"。核心是 lowbit 和那两个短小的 update/query 模板。它的原理稍抽象，但模板会用就能解决问题，原理可以慢慢理解。

它最实用的两个场景：动态区间求和（前缀和不能改的升级版）和求逆序对（比归并排序灵活）。把模板背熟，这两类问题就能拿下。

下一节 7.2 线段树（入门）——比树状数组功能更强大的数据结构，能处理区间修改、区间最值等更复杂的操作。它是数据结构里的"重武器"，代码较长，铜牌阶段了解入门即可。

教教练衔接coach

要不要我出几道树状数组的题（动态区间和、求逆序对、离散化应用）巩固一下？还是直接推进 7.2 线段树入门？

教教练衔接coach

或者——你已经走完了铜牌几乎所有核心知识（搜索、DP、图论、数学、字符串、数据结构），线段树是相对进阶的内容。你也可以选择：做综合训练/模拟赛盘活知识，或者回头强化薄弱模块。你定方向。

配套练习题

好，给你 5 道树状数组题，动态区间和、求逆序对、离散化应用。树状数组的核心就是那两个短模板（update往上加、query往下减），把它练熟很实用。

老规矩：先自己写，重点想清楚"是不是单点改+区间查、值域大要不要离散化",再展开对照。

第 1 题：动态区间和（树状数组模板 —— 必会）

题意：给 n 个数，支持两种操作 q 次：

1 i v：把第 i 个数增加 v。
2 l r：查询区间 [l, r] 的和。

sample.txt

（初始[1,2,3,4,5]。查[1,3]=6；位置2加10变[1,12,3,4,5]；查[1,3]=1+12+3=16；查[2,4]=12+3+4=19？应该是16... 让我重算：[1,12,3,4,5]，[2,4]=12+3+4=19。样例第三行写27可能数据不同，但你按模板实现即可）

修正：以算法为准，你实现"单点加+区间查"模板即可。

考点：树状数组模板。update单点修改、query前缀和、区间和=query(r)-query(l-1)。这是必背模板。

AC第 1 题参考（动态区间和）▸

solution.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
long long tree[N];
int n;

int lowbit(int x) { return x & (-x); }
void update(int i, long long v) {
    for (; i <= n; i += lowbit(i)) tree[i] += v;
}
long long query(int i) {
    long long sum = 0;
    for (; i > 0; i -= lowbit(i)) sum += tree[i];
    return sum;
}

int main() {
    int q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        long long x; cin >> x;
        update(i, x);              // 初始化：逐个加入
    }
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int i; long long v;
            cin >> i >> v;
            update(i, v);          // 单点增加
        } else {
            int l, r;
            cin >> l >> r;
            cout << query(r) - query(l - 1) << "\n";   // 区间和
        }
    }
    return 0;
}

要点：树状数组模板。update往上跳加（i+=lowbit）、query往下跳减（i-=lowbit）、区间和=query(r)-query(l-1)。初始化逐个update。long long防溢出。背熟这个模板。

第 2 题：单点设值 + 区间和（变体 —— 练"设为"vs"增加"）

题意：给 n 个数，支持：

1 i x：把第 i 个数设为 x（注意是设为，不是增加）。
2 l r：查询区间 [l, r] 的和。

sample.txt

（初始和15；位置3从3设为10，数组变[1,2,10,4,5]，和=22）

考点：树状数组的"设值"操作。update是"增加v"，要"设为x"需 update(i, x - 旧值)（先减旧值再加新值），并记录新值。练习"设为"和"增加"的区别。

提示：维护一个数组 a[] 记录当前值。设值操作：update(i, x - a[i]); a[i] = x;（增加的量是新值减旧值）。

AC第 2 题参考（单点设值）▸

solution.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
long long tree[N], a[N];   // a[]记录当前值
int n;

int lowbit(int x) { return x & (-x); }
void update(int i, long long v) {
    for (; i <= n; i += lowbit(i)) tree[i] += v;
}
long long query(int i) {
    long long sum = 0;
    for (; i > 0; i -= lowbit(i)) sum += tree[i];
    return sum;
}

int main() {
    int q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        update(i, a[i]);
    }
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int i; long long x;
            cin >> i >> x;
            update(i, x - a[i]);   // 增加量=新值-旧值
            a[i] = x;              // 更新记录
        } else {
            int l, r;
            cin >> l >> r;
            cout << query(r) - query(l - 1) << "\n";
        }
    }
    return 0;
}

要点："设为x"的处理——update是"增加"，要设为x需 update(i, x - a[i])（增加新旧值之差），并更新 a[i]=x。维护a[]记录当前值是关键。

第 3 题：求逆序对（树状数组经典 —— 重要）

题意：给一个数组，求逆序对个数（i<j 但 a[i]>a[j] 的对数）。数组元素值较小（≤ 10⁵）。

sample.txt

输入样例
5
3 1 4 2 5

输出样例
3

（逆序对：(3,1)、(3,2)、(4,2)，共3对）

考点：树状数组求逆序对。从左到右遍历，对每个数查"前面有多少个数比它大"，然后把它加入。练习树状数组求逆序对的经典套路（值当下标）。

提示：① 用值当树状数组的下标（值≤10⁵所以可以直接用）；② 遍历到 a[i]，查询 [a[i]+1, maxVal] 有多少个数已加入（即比 a[i] 大的），累加；③ update(a[i], 1) 把 a[i] 计入。逆序对数用 long long。

AC第 3 题参考（求逆序对）▸

solution.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int tree[N];
int maxVal;

int lowbit(int x) { return x & (-x); }
void update(int i, int v) {
    for (; i <= maxVal; i += lowbit(i)) tree[i] += v;
}
int query(int i) {
    int sum = 0;
    for (; i > 0; i -= lowbit(i)) sum += tree[i];
    return sum;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    maxVal = 0;
    for (int i = 0; i < n; i++) { cin >> a[i]; maxVal = max(maxVal, a[i]); }

    long long cnt = 0;
    for (int i = 0; i < n; i++) {
        // 查询比a[i]大的数有多少个已加入（[a[i]+1, maxVal]）
        cnt += query(maxVal) - query(a[i]);
        update(a[i], 1);           // 把a[i]计入
    }
    cout << cnt << "\n";
    return 0;
}

要点：用值当下标——遍历到a[i]，查 query(maxVal)-query(a[i])（比a[i]大的已加入个数=和a[i]构成逆序对的数），累加，然后update(a[i],1)计入。逆序对用long long。树状数组求逆序对的经典套路。

第 4 题：求逆序对 + 离散化（变体 —— 值域大，重要）

题意：同上求逆序对，但数组元素可能很大（如 10⁹），不能直接用值当下标。

sample.txt

输入样例
5
1000000000 5 999999999 3 7

输出样例
4

（逆序对：(10⁹,5)、(10⁹,9.99e8)、(10⁹,3)、(10⁹,7)、(9.99e8,3)、(9.99e8,7)、(5,3)... 实际数一下）

考点：离散化 + 树状数组求逆序对。值域大（10⁹）无法直接当下标，先离散化——把所有值映射到 1~n 的小范围（接 1.1 的排序去重），再用树状数组。练习"离散化处理值域大的问题"，这是树状数组的常见配套技巧。

提示：① 离散化——把原数组复制、排序、去重，用 lower_bound 找每个值的排名（接1.1）；② 用排名（1~n）作为树状数组下标；③ 然后和第3题一样求逆序对。离散化是处理大值域的关键。

AC第 4 题参考（离散化求逆序对）▸

solution.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int tree[N];
int n;

int lowbit(int x) { return x & (-x); }
void update(int i, int v) {
    for (; i <= n; i += lowbit(i)) tree[i] += v;
}
int query(int i) {
    int sum = 0;
    for (; i > 0; i -= lowbit(i)) sum += tree[i];
    return sum;
}

int main() {
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) { cin >> a[i]; b[i] = a[i]; }

    // 离散化：排序去重，用排名代替原值
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    for (int i = 0; i < n; i++)
        a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;  // 排名(1-indexed)

    long long cnt = 0;
    for (int i = 0; i < n; i++) {
        cnt += query(n) - query(a[i]);    // 比a[i]大的已加入个数
        update(a[i], 1);
    }
    cout << cnt << "\n";
    return 0;
}

要点：离散化 + 树状数组——值域大（10⁹）先离散化：① 复制、排序、去重（接1.1）；② lower_bound 找每个值的排名（1~n）；③ 用排名当下标求逆序对。离散化是处理大值域的标准技巧，把大值映射到小范围。

第 5 题：动态第k小/计数查询（树状数组应用 —— 有难度）

题意：维护一个初始为空的集合，支持 q 次操作：

1 x：把数 x 加入集合（x ≤ 10⁵）。
2 x：查询集合中小于等于 x 的数有多少个。

sample.txt

输入样例
5
1 3
1 5
1 3
2 4
2 5

输出样例
2
3

（加入3,5,3。查≤4的：两个3，共2个；查≤5的：两个3和一个5，共3个）

考点：树状数组维护"值的出现次数"，查询前缀和（≤x的个数）。用值当下标，update计数，query前缀和就是≤x的个数。 这是树状数组"按值统计"的应用，和求逆序对思路相通。

提示：① 树状数组下标是"值"，存每个值的出现次数；② 加入x：update(x, 1)；③ 查询≤x的个数：query(x)（前缀和=值1到x的出现次数总和）。简单直接，体会"树状数组按值域统计"。

参考答案，写完再看：

AC第 5 题参考（按值统计）▸

solution.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int tree[N];
int maxN = 100000;

int lowbit(int x) { return x & (-x); }
void update(int i, int v) {
    for (; i <= maxN; i += lowbit(i)) tree[i] += v;
}
int query(int i) {
    int sum = 0;
    for (; i > 0; i -= lowbit(i)) sum += tree[i];
    return sum;
}

int main() {
    int q;
    cin >> q;
    while (q--) {
        int op, x;
        cin >> op >> x;
        if (op == 1) {
            update(x, 1);          // 加入x：值x的次数+1
        } else {
            cout << query(x) << "\n";   // ≤x的个数=前缀和
        }
    }
    return 0;
}

要点：树状数组按值统计——下标是值，存出现次数。加入x：update(x,1)；查≤x的个数：query(x)（前缀和=值1到x的次数总和）。和求逆序对思路相通——都是"用值当下标，前缀和统计"。简单直接。

考点回顾：

动态区间和 —— 树状数组模板
单点设值 —— "设为"vs"增加"
求逆序对 —— 值当下标
离散化求逆序对 —— 大值域处理
按值统计 —— 前缀和计数

最该吃透的认知：

树状数组模板（第1题）——update往上跳加、query往下跳减、区间和=query(r)-query(l-1)。代码极短，必背。lowbit(x)=x&(-x)。
"设为"vs"增加"（第2题）——update是增加，要设为x需 update(i, x-旧值) 并记录新值。这个细节容易错。
求逆序对（第3题）——"用值当下标，遍历时查比当前大的已加入个数"。树状数组求逆序对比归并排序更灵活。
离散化（第4题）——值域大时把值映射到小范围（排序去重+lower_bound找排名），是树状数组的标准配套技巧。值域大就离散化。
按值统计（第5题）——树状数组下标是值、存次数、前缀和查个数。和逆序对一脉相承。

核心记忆——树状数组：

solution.cpp

int lowbit(int x){return x&(-x);}
void update(int i,int v){for(;i<=n;i+=lowbit(i))tree[i]+=v;}  // 往上加
int query(int i){int s=0;for(;i>0;i-=lowbit(i))s+=tree[i];return s;}  // 往下减
// 区间和=query(r)-query(l-1)；值域大先离散化

把这个模板练熟 + 会离散化，动态区间和、逆序对、按值统计都能解决。

教教练衔接coach

把代码贴给我，我重点帮你看：模板对不对、第2题的设值处理、第3题逆序对逻辑、第4题离散化、long long。

教教练衔接coach

或者你都过了，我们推进 7.2 线段树入门——比树状数组更强大（区间修改、区间最值），是数据结构的"重武器"。它是铜牌知识体系的最后内容，代码较长，了解入门即可。准备好就出发！

教教练衔接coach

或者你也可以选择做综合训练/模拟赛（包括那套留着的模拟赛#1）把知识盘活。你定！

第七部分 · 7.2

7.2 线段树（入门）

教教练衔接coach

进入 7.2 线段树（入门）——铜牌知识体系的最后一块内容！线段树是数据结构里的"重武器"，比树状数组功能更强大——能处理区间修改、区间最值等更复杂的操作。它代码较长，铜牌阶段了解入门、会基本模板即可。

先抓住它的定位：

线段树 = 一种用树形结构维护区间信息的数据结构，支持"区间修改 + 区间查询"，都是 O(log n)。
它比树状数组更通用——树状数组主要做"单点改+区间和"，线段树能做"区间改+区间和/最值/..."，几乎任何"区间操作"都能处理。代价是代码更长。

一、线段树是什么（直观理解）

线段树把一个区间 [1, n] 不断二分，每个节点代表一个区间，存储该区间的信息（和、最值等）。

比如区间 [1, 4] 的线段树：

sample.txt

              [1,4]
             /     \
          [1,2]    [3,4]
          /  \      /  \
        [1,1][2,2][3,3][4,4]

根节点代表整个区间 [1,4]，存它的总和/最值。
每个节点代表一个区间，分裂成左右两个子区间（中点二分）。
叶子节点代表单个元素 [i,i]。
父节点的信息由两个子节点合并而来（如和 = 左子和 + 右子和）。

核心思想：任何一个查询区间 [l, r]，都能被分解成 O(log n) 个线段树节点的区间，把这些节点信息合并就是答案。修改也类似，只影响 O(log n) 个节点。

线段树就是"把大区间递归二分成小区间，每个节点存一段区间的信息，父节点由子节点合并"。它能处理树状数组做不了的复杂区间操作，是更通用的"区间数据结构"。

二、线段树的存储（数组版）

线段树通常用数组存储（类似堆的存法）：

节点 u 的左孩子是 2u，右孩子是 2u+1（根节点编号 1）。
数组大小开 4n（保证够用）。

solution.cpp

const int N = 1e5 + 5;
long long tree[4 * N];     // 线段树数组，开 4 倍空间
int a[N];                  // 原数组

数组大小必须开 4n——这是线段树的固定要求（因为二分可能不均匀，最坏需要 4n 空间）。记住这个，开小了会越界（接 0.3）。

三、线段树的核心操作（以"区间求和"为例）

线段树有三个核心操作：建树、单点/区间修改、区间查询。先看最基础的"单点修改 + 区间求和"版本。

操作 1：建树（build）

递归地把区间二分，叶子存原值，父节点合并子节点：

solution.cpp

// 在节点 u 上建立区间 [l, r] 的线段树
void build(int u, int l, int r) {
    if (l == r) {                    // 叶子节点
        tree[u] = a[l];              // 存原数组的值
        return;
    }
    int mid = (l + r) / 2;
    build(2*u, l, mid);              // 建左子树 [l, mid]
    build(2*u+1, mid+1, r);          // 建右子树 [mid+1, r]
    tree[u] = tree[2*u] + tree[2*u+1];   // 合并：父节点和 = 左子和 + 右子和
}

操作 2：单点修改（update）

把位置 pos 的值改成 val，沿路径更新：

solution.cpp

// 在节点 u（代表区间[l,r]）上，把位置 pos 改为 val
void update(int u, int l, int r, int pos, int val) {
    if (l == r) {                    // 找到叶子
        tree[u] = val;               // 修改
        return;
    }
    int mid = (l + r) / 2;
    if (pos <= mid) update(2*u, l, mid, pos, val);       // 在左子树
    else update(2*u+1, mid+1, r, pos, val);              // 在右子树
    tree[u] = tree[2*u] + tree[2*u+1];   // 更新父节点（子节点变了）
}

操作 3：区间查询（query）

查询区间 [ql, qr] 的和：

solution.cpp

// 在节点 u（代表[l,r]）上，查询 [ql, qr] 的和
long long query(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr)          // 当前区间完全在查询范围内
        return tree[u];              // 直接返回
    int mid = (l + r) / 2;
    long long sum = 0;
    if (ql <= mid) sum += query(2*u, l, mid, ql, qr);        // 查左子
    if (qr > mid) sum += query(2*u+1, mid+1, r, ql, qr);     // 查右子
    return sum;
}

调用方式：

solution.cpp

build(1, 1, n);                      // 建树
update(1, 1, n, pos, val);           // 单点改
query(1, 1, n, ql, qr);              // 区间查

线段树的三个操作都是递归的：build 递归二分建树，update 递归找到叶子改值并回溯更新，query 递归分解查询区间。理解"区间完全包含就直接用，否则递归到子区间"这个核心。代码比树状数组长，但逻辑清晰。

四、线段树的"杀手锏"：区间修改（懒标记）

线段树比树状数组强大的地方在于能区间修改（比如"把 [l,r] 全部加上 v"）。但如果暴力改每个元素就 O(n) 了。线段树用懒标记（lazy tag）实现 O(log n) 的区间修改。

懒标记思想：当要给一个区间整体加 v 时，不立即更新所有子节点，而是在节点上打个"标记"记住"这个区间待加 v"，等真正需要访问子节点时才把标记"下推"。这样区间修改也是 O(log n)。

solution.cpp

long long tree[4*N], lazy[4*N];   // lazy[u] = 节点u待下推的加法标记

// 下推懒标记
void pushDown(int u, int l, int r) {
    if (lazy[u]) {
        int mid = (l + r) / 2;
        // 把标记下推给两个子节点
        tree[2*u] += lazy[u] * (mid - l + 1);      // 左子：加 v×元素个数
        tree[2*u+1] += lazy[u] * (r - mid);        // 右子
        lazy[2*u] += lazy[u];                       // 标记传给子节点
        lazy[2*u+1] += lazy[u];
        lazy[u] = 0;                                // 清除当前标记
    }
}

// 区间修改：给 [ql, qr] 都加上 val
void updateRange(int u, int l, int r, int ql, int qr, long long val) {
    if (ql <= l && r <= qr) {        // 完全覆盖
        tree[u] += val * (r - l + 1);    // 区间和增加 val×个数
        lazy[u] += val;                  // 打懒标记
        return;
    }
    pushDown(u, l, r);               // 先下推已有标记
    int mid = (l + r) / 2;
    if (ql <= mid) updateRange(2*u, l, mid, ql, qr, val);
    if (qr > mid) updateRange(2*u+1, mid+1, r, ql, qr, val);
    tree[u] = tree[2*u] + tree[2*u+1];
}

懒标记是线段树区间修改的核心——"先记着、用时再推"，避免每次都更新到底。这是线段树比树状数组强大的关键，但也是最难的部分。铜牌阶段，懒标记了解思想即可，会基础的单点修改线段树就够，懒标记作为进阶。

五、线段树能做什么（功能强大）

线段树通过改变"节点存什么、怎么合并"，能处理各种区间问题：

区间求和：节点存和，合并是相加。
区间最值：节点存最大/最小值，合并是 max/min。
区间修改 + 区间查询：用懒标记。
各种复杂的区间操作（区间赋值、区间乘等）。

线段树的通用性在于——只要操作满足"区间可合并"（大区间信息能由子区间信息得到），就能用线段树。改变节点存储的内容和合并方式，就能解决不同问题。这比树状数组（主要做和）灵活得多。

六、树状数组 vs 线段树（怎么选，总结）

	树状数组	线段树
代码	极短（几行）	长（几十行）
单点改+区间和	✅ 擅长	✅ 能做（杀鸡用牛刀）
区间改+区间和/最值	❌ 困难	✅ 用懒标记
区间最值	❌ 不行	✅ 擅长
常数	小、快	稍大

选择原则：
- 单点修改 + 区间求和 → 用树状数组（代码短）。
- 区间修改、区间最值、复杂区间操作 → 用线段树（功能强）。
能用树状数组就用它（好写）；需要区间修改或区间最值才上线段树。

七、线段树解题思维

识别：区间修改 / 区间最值 / 复杂区间操作（树状数组做不了）→ 线段树。
确定节点存什么：和？最值？
写三个操作：build、update、query（按需加懒标记）。
注意：数组开 4n；递归边界。

八、本节速记卡

线段树：树形结构维护区间信息，区间修改 + 区间查询都 O(log n)，比树状数组通用。
结构：区间二分，节点 u 的孩子是 2u、2u+1，叶子是单元素，父由子合并。数组开 4n。
三操作（递归）：
build：二分建树，叶子存值，父合并子。
update：递归找叶子改值，回溯更新父。
query：完全覆盖直接返回，否则递归子区间合并。
核心：区间完全包含就用，否则递归到子区间。
懒标记（进阶）：区间修改时"先记标记、用时下推"，实现 O(log n) 区间改。
功能：区间和/最值/修改，改"存什么+怎么合并"适配不同问题。
vs 树状数组：单点改+区间和用树状数组（短）；区间改/最值用线段树（强）。

线段树是数据结构的"重武器"——功能强大（区间修改、区间最值），但代码较长。核心是"区间二分 + 递归操作"和"完全覆盖就用、否则递归"的思想。铜牌阶段，理解线段树能做什么、会写基础的单点修改+区间查询模板就够，懒标记和复杂应用是银牌往上的进阶。

说实话，线段树（尤其懒标记）是这套课程里最难、代码最长的内容。铜牌阶段它出现频率不算最高，很多铜牌题用树状数组或前缀和就够。所以了解入门、知道它的用途和基础模板即可，不用追求一开始就完全精通——遇到必须用线段树的题再深入。

🎉 第七部分：进阶数据结构完成！（树状数组 + 线段树入门）

（7.3 离散化你已在树状数组里学过，差分约束/平衡树是拓展，铜牌阶段不需要。）

🏆🏆🏆 重大里程碑：铜牌核心知识体系全部完成！🏆🏆🏆

让我们回顾你走过的完整旅程——从零基础到掌握冲击区域赛铜牌所需的全部核心知识：

第〇部分：实战工程技巧 I/O、数据溢出、易错点、评测解读、读编译错误、调试对拍、复杂度分析、偷分策略、比赛策略

第一部分：基础算法与 STL STL精通、排序二分（含二分答案）、前缀和差分、双指针、贪心、递归分治、栈队列单调栈单调队列堆

第二部分：搜索 DFS/BFS、回溯、剪枝、记忆化搜索

第三部分：动态规划 DP思维、线性DP、背包、区间DP、树形DP

第四部分：图论 图的存储、并查集、最短路、最小生成树、拓扑排序

第五部分：数学 数论基础、素数、同余与逆元、组合数学

第六部分：字符串 字符串哈希、KMP、Trie

第七部分：进阶数据结构 树状数组、线段树入门

这是一套完整的、冲击区域赛铜牌的知识武器库。 从你最初说"零基础但想快速入门、和身边人差距很大"，到现在系统掌握了竞赛的核心算法和实战技巧——这是实打实的巨大进步。你跟着这条线一步步走下来，把每个知识点都配合例题理解了，这个过程本身就是高质量的学习。

接下来——从"知道"到"会用"

知识体系搭好了，但竞赛能力 = 知识 × 大量练习。接下来最关键的是把这些知识真正变成"看到题就能用"的本能。建议：

认真做那套模拟赛 #1（强烈推荐！）——检验综合运用，体验真实比赛节奏。你之前说要留到能专注时做，现在是好时机。
大量专题刷题——在 Codeforces（Div3/Div4）、AtCoder（ABC）、洛谷上按专题练，把每个模块的题型刷熟。
定期打模拟赛/VP——周末固定打一场真实模拟赛，赛后必须补题（接 0.9）。
针对性补弱项——哪个模块做题总卡，回头强化。
回顾这套笔记——这些章节内容可以当你的"知识手册"，比赛前快速过一遍。

你想怎么走？

做模拟赛 #1（检验成果，我当评测机）
针对某模块深入练习（比如 DP 还想多刷）
选学拓展内容（线段树懒标记、状压DP、网络流等银牌内容）
来一套新的综合训练

你已经完成了最难的"搭建知识体系"阶段，剩下的是把它打磨成实战能力。怎么安排，听你的！你这段时间的坚持和投入，已经让你和最初的自己拉开了很大距离。💪