虽然说:“一般普及组集训不会讲线段树,所以即便听不懂,也没有什么关系。”

但是我们也必须学好。

线段树是快速的查找某一个节点在若干条线段中出现的次数,RMQ也常常使用线段树来实现。

线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。

使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,实际应用时一般还要开4N的数组以免越界,因此有时需要离散化让空间压缩。

—— 百度百科

eg1:《动态成绩查询》

一个班里有n名学生,他们的学号是1~n

起初,所有人的成绩都是0,有m次操作。

  • 给x加分或者减分
  • 给定l,r求区间和

数据范围是很经典的$10^{5}$。

建立一个树,根是1~n的区间和,左孩子和有孩子是1~mid和mid~n,叶子节点为单个学生。

给x加分即给x的所有父节点加分,这就是线段树。

我们使用堆式存储存下整个树。

虽然说是有10w个节点,但是我们不能只开10w,我们要开2的整次幂,且接近10w。而$2^17$可以满足条件。

我们定义w[]存储一个节点的值。

单点加

我们单点加可以从叶子节点开始加,叶子节点加完后直接/2来到父节点。

void pointAdd(int pos, int k) {
    // 找到 pos 在 w[] 位于什么位置
    int cur = SIZE + pos - 1;   // 例如,1号同学位于 w[131072]

    while(cur != 0) {
        w[cur] += k;
        cur = cur / 2;
    }
}

区间求和

如果要查询的区间就在自己的管辖范围之内,直接返回即可。如果不在就交给自己的孩子节点去做。


// 查询 [queryLe, queryRt] 的区间和
// querySum 要返回所查的那些元素,落在 node 管辖区间里面的这部分的 sum
// querySum 只管 「node 管辖区间」与「查询区间」的交集元素,其余的不管
int querySum(int node, int fieldLe, int fieldRt, int queryLe, int queryRt) {
    if(queryRt < fieldLe || fieldRt < queryLe)
        return 0;       // 查询区间的右端点比管辖区间的 l 还小,显然本次查询不关这个 node 的事
    if(queryLe <= fieldLe && fieldRt <= queryRt)
        return w[node]; // 查询区间完全覆盖掉了 node 的管辖区间,返回 w[node],即管辖区间的 sum
    // 例如,查询 [1, 100],而管辖区间是 [9, 16]
    // 那我显然直接返回 sum(9, 16)

    // 现在,查询区间和管辖区间有交集,需要细化处理
    int mid = (fieldLe + fieldRt) / 2;

    // 由左儿子查询、右儿子查询,返回它们的和
    // 左儿子会处理自己管辖区域内的 sum,右儿子同理
    int sumLe = querySum(node*2, fieldLe, mid, queryLe, queryRt);
    int sumRt = querySum(node*2+1, mid+1, fieldRt, queryLe, queryRt);
    return sumLe + sumRt;
}

eg2RMQ:洛谷P1816《忠诚》

我们在给区间加的时候顺手统计最小值即可。

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

int n, m;       // n 个学生,m 次操作

void input() {
    cin >> n >> m;
}

// 维护一个长度为 131072(i.e. 2^17)长度的序列
#define SIZE 131072

int w[SIZE * 2 + 5];    // w[x]: x结点所管辖区间的 sum
// w[1] 的管辖区间是 [1, 131072]
// w[2]: [1, 65536], w[3]: [65537, 131072]
// ...
// w[131072]: [1, 1], ....

// 给 pos 同学加 k 分
// 目前正在处理 node 结点,它的管辖区间是 [fieldLe, fieldRt]
void pointAdd(int node, int fieldLe, int fieldRt, int pos, int k) {
    // 更新 node 管辖区域的 sum 
    w[node] += k;

    // 如果已经处理到底层,则更新 w 之后直接返回
    if(fieldLe == fieldRt) return;

    // 还需要递归处理
    // 左半块:编号是 node*2, 管辖区间 [fieldLe, mid]
    // 右半块:编号是 node*2+1, 管辖区间 [mid+1, fieldRt]
    int mid = (fieldLe + fieldRt) / 2;

    // 例如:node 管辖区间是 [8, 16]
    // mid = (8+16)/2 = 12,左半块的管辖区间是 [8, 12];右半块 [13, 16]
    
    if(pos <= mid)      // 如果 pos 落在左半块,则递归给左边半块
        pointAdd(node*2, fieldLe, mid, pos, k);
    else
        pointAdd(node*2+1, mid+1, fieldRt, pos, k);
}

// 查询 [queryLe, queryRt] 的区间和
// querySum 要返回所查的那些元素,落在 node 管辖区间里面的这部分的 sum
// querySum 只管 「node 管辖区间」与「查询区间」的交集元素,其余的不管
int querySum(int node, int fieldLe, int fieldRt, int queryLe, int queryRt) {
    if(queryRt < fieldLe || fieldRt < queryLe)
        return 0;       // 查询区间的右端点比管辖区间的 l 还小,显然本次查询不关这个 node 的事
    if(queryLe <= fieldLe && fieldRt <= queryRt)
        return w[node]; // 查询区间完全覆盖掉了 node 的管辖区间,返回 w[node],即管辖区间的 sum
    // 例如,查询 [1, 100],而管辖区间是 [9, 16]
    // 那我显然直接返回 sum(9, 16)

    // 现在,查询区间和管辖区间有交集,需要细化处理
    int mid = (fieldLe + fieldRt) / 2;

    // 由左儿子查询、右儿子查询,返回它们的和
    // 左儿子会处理自己管辖区域内的 sum,右儿子同理
    int sumLe = querySum(node*2, fieldLe, mid, queryLe, queryRt);
    int sumRt = querySum(node*2+1, mid+1, fieldRt, queryLe, queryRt);
    return sumLe + sumRt;
}

void work() {
    while(m--) {
        int cmd, x, y;
        cin >> cmd >> x >> y;

        if(cmd == 1)
            pointAdd(1, 1, SIZE, x, y);     // 交给 1 号结点,其管辖区间是 [1, SIZE]
        else
            cout << querySum(1, 1, SIZE, x, y) << endl;     // 交给 1 号点,1 号的管辖区间是全集
    }
}

int main() {
    input();
    work();

    return 0;
}
This post was written on July 27, 2022