树状数组与线段树

树状数组

线段树使用范围更广，完全包含树状数组的应用范文。但树状数组相较于线段树，有以下好处

代码非常简短，好些
运行效率很高，常数很小，一般比线段树快10倍左右

树状数组的核心用途是动态快速地求解前缀和，有时也用于求最大值

树状数组可以在$O(log(n))$的复杂度内进行以下两个操作：

单点修改：将某个位置上的数加上一个数

要将x变成v的话，可以加上v-x
区间查询：求某一个前缀和

屏幕截图 2023-03-05 171933

前缀和算法在序列不用修改时区间查询效率为$O(1)$效率更高，但涉及修改会很麻烦

算法	单调修改	区间插叙	总体时间复杂度
前缀和	$O(n)$	$O(n)$	$O(n)$
树状数组	$O(logn)$	$O(logn)$	$O(logn)$

树状数组本质上只能用于单点修改和区间查询，其他问题要使用树状数组要先进行转化，如单点查询、区间修改，这两种操作都要借助差分思想进行转化。

数据结构的选择要看具体需要什么操作，而不是题型

树状数组

具体实现

树状数组是一个一维数组，下标从1开始，每个位置存储的都是一段数的和，存储规则如下：

第0层：所有奇数（不能整除$2^1$）的下标的位置作为第0层，直接存原数组对应数值
第1层：所有能够整除$2^{1$但不能整除$2}2$的下标的位置作为第1层，存储最接近的一个第0层值和本身位置对应的值的和
第2层：所有能够整除$2^{2$但不能整除$2}3$的下标的位置作为第1层，存储最接近的一个第0、1层值和本身位置对应的值的和
第n层：所有能够整除$2^{n$但不能整除$2}{n+1}$的下标的位置作为第1层，存储下面所有层下标小于且最接近当前下标的位置的树状数组存储值和本身位置对应的原数组值的和

层数定义规则：下标对应二进制表示的末尾有几个0就在第几层

区间范围规则：若x的二进制表示最后有k个0，则其存储区间$[x-2^k+1, x]$范围内的和，
$$
\begin{align}
& = \sum [x-2^k+1, x] \\
& = \sum [x-lowbit(x)+1, x] \\
\end{align}
$$
此公式是树状数组核心公式！

求解二进制末尾有几个0可以使用$lowbit$位运算，
$$
lowbit(x) = x \ & -x = 2^k
$$
$2^k$对应于末尾的1对应的数值大小，k对应于末尾0的个数

树状数组的性质：

每个内部节点c[x]保存以它为根的子树中的所有叶节点的和
每个内部节点c[x]的子节点个数等于lowbit(x)的位数，eg. lowbit(16) = 10000 = 5
除树根外, 每个内部节点c[x]的父节点是c[x+lowbit(x)]，eg. c[7]–> c[7+1] = c[8]`
树的深度为$O(logN)$

如果N不是2的整次幂, 那么树状数组就是一个具有同样性质的森林结构
c[x]存的是原序列a的区间[x-lowbit(x)+1, x]`中所有数的和

每个节点都有唯一的父节点$x+lowbit(x)$

操作实现

单点修改：

每修改一个点，会影响$logn$个点

// A[x] + v
// 正向修改，每个节点都有唯一的父节点x+lowbit(x)
// 只有c[x]和它所有的祖宗节点保存的"区间和" 包含a[x]
// 在x位置加上v，并将后面相关联的位置也加上v
void add(int x, int v){
    for (i = x; i <= n; i += lowbit(x)) c[x] += v
}

区间查询（求某一个前缀和）：

+ C[x - lowbit(x)] + \ldots $

// 询问x的前缀和
int qurey(int x){
    int res = 0;
	// 逆序递归求和
	for (i = x; i > 0; i -= lowbit(i)) res += c[i];
	return res
}

初始化

执行所有操作之前, 我们需要对树状数组做初始化——针对原始序列a, 初始化一个树状数组c。
- 一般的方法：建立一个全为0的数组c, 然后对每个x执行add(x, a[x])，时间复杂度为$O(NlogN)$ ，通常采用这种初始化就已经足够
- 更加高效的做法: 从小到大依次考虑每一个节点x, 借助lowbit运算扫描他的子节点并求和, 上述树形结构的每条边只会被遍历一次，时间复杂度为$ O(N) $
  1
  2
  3
  4
  5
  预处理一个前缀和数组 pre
  // 初始化树状数组 c
  for(int i =1;i<=n;i++){
  c[i] = pre[i] - pre[i-lowbit(i)]; // O(N);
  }

C++

// 树状数组——AcWing 1264. 动态求连续区间和
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>

using namespace std;

const int N = 100010;

int n, m;
int a[N], tr[N];

// x的二进制表示最后有k个0，则树状数组中结点c[x]存储(x - 2^k, x]即(x - lowbit(x), x]这一区间的和
int lowbit(int x){
    return x & -x; // 位运算，返回x最右端一位的1所代表的大小（最后有k个0，则求得值为2^k）
    // 寻找树状数组中的父结点或子结点
}

// 端点修改
// x表示修改下标，v表示加上的值
void add(int x, int v){
    // 树状数组下标从1开始，所以要 <= n
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
    // 树状数组中每个结点i的父节点为i + lowbit(i)
    // 要改变一个结点的值，还要改变其所有祖先节点的值
}

// 区间查询
int query(int x){
    // 求解[1, x]的前缀和
    int res = 0; 
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
    // 将当前结点和其所以子孙节点相加即求得前缀和
    // 由于不能被2整除（最右端的1在最后一位）的数都放在了叶子结点，所以最终会加上它和它前面的元素的和
}

int main(){
    scanf("%d%d", &n, &m);
    // 树状数组下标从1开始
    for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++ i) add(i, a[i]);
    // 默认刚开始树状数组所有元素为0，使用add()函数自动进行初始化（将初始化等同于单点修改）
    while (m --){
        int k, x, y;
        scanf("%d%d%d", &k, &x, &y);
        // 区间查询
        if (k == 0) printf("%d\n", query(y) - query(x - 1)); // 差分求解任意区间
        // 单点修改
        else add (x, y);   
    }

    return 0;
}

Python

# 树状数组——AcWing 1264. 动态求连续区间和
def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    tr = [0] * (n + 1) # 树状数组下标从1开始
    
    def lowbit(x):
        return x & -x
    
    def add(x, v):
        while x <= n:
            tr[x] += v
            x += lowbit(x)
    
    def query(x):
        res = 0
        while x > 0:
            res += tr[x]
            x -= lowbit(x)
        return res
    
    # 初始化树状数组，可以看做原数组a是全0数组，每次改变a数组一位的值
    # 树状数组下标从1开始
    for i in range(1, n + 1):
        add(i, a[i - 1]) # 由于a从0开始，所以是i - 1
    
    for _ in range(m):
        k, a, b = map(int, input().split())
        # 区间查询
        if not k:
            print(query(b) - query(a - 1)) # 前缀和形式的查询，注意是a-1
        # 单点修改
        else:
            add(a, b)

if __name__ == "__main__":
    main()

本题看上去很复杂，需要用二维数据结构，使用二维数组存储。但是认真读题可以发现，输入的格式是按y坐标的增序给出的，这意味着在其后出现的点都与其无关，只用关心其前面的点。换句话说，只要我们边读入边处理，而不是全读入再处理，问题就能大大化简。由于y坐标相同的按x坐标增序给出，所以不用考虑y坐标的问题（y坐标一定满足在其左下方）。因而只用考虑x坐标的问题。这就实现了问题的降维简化，将二维将降成一维。这里降成一维的意思是我们不用使用二维数组来存储，而只需统计每个x坐标当前有的星星数。而当前星星的级数就是x下标小于其的前缀和。

具体来说，级数k等于前面所有点中x坐标小于等于其的所有点数之和。这显然可以转化为一个前缀和问题，由于每个x坐标对应的点数不是固定不变的，而是随着输入而循环增加。这就涉及单点修改的问题，可以使用树状数组。

屏幕截图 2023-03-05 214259

我们计算一个点 $(x_i, y_i)$ 的优先级，就是计算满足$x \le x_i$ 且 $y \le y_i$ 的点的数量

因为 $y$ 按照从小到大顺序输入的，因此对于新加入的元素 $(x_i, y_i)$，$\forall y \in [y_0, y_{i - 1}]$，都有 $y_i > y$

于是对于新加入的元素 $(x_i, y_i)$，他的优先级，就是在他之前加入的所有元素中 $x < x_i$ 的点的个数。观察到一个边插入边求前缀和的数据结构，想到了树状数组

C++

// 树状数组——AcWing 1265. 数星星
// 本题关键在于
// 1.边读取边处理，将问题降维化简 
// 2. 认识到数据所需的本质操作——单点修改和区间查询，从而选择树状数组
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 32010;

int n;
int tr[N], level[N];
// tr存储树状数组，

int lowbit(int x){
    return x & -x;// 位运算，返回x最右端一位的1所代表的大小（最后有k个0，则求得值为2^k）
    // 寻找树状数组中的父结点或子结点
}

// 单点修改
void add(int x, int v){
    // 注意这里是到N而不是n，n是节点数量，但树状数组范围是x坐标的范围
    for (int i = x; i <= N; i += lowbit(i)) tr[i] += v;
    // 树状数组中每个结点i的父节点为i + lowbit(i)
    // 要改变一个结点的值，还要改变其所有祖先节点的值
}

// 计算每个x坐标对应的级别
// 区间查询
int query(int x){
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i){
        int x, y;
        scanf("%d%d", &x, &y);
        x ++; // 注意前缀和存储时一般从1开始，因为整体后移一位
        // 先求级数再插入，防止把自身算入
        level[query(x)] ++; // 边读取边处理，并记录每个级别的数量
        add(x, 1); // 级别增加1
    }
    for (int i = 0; i < n; ++ i) printf("%d\n",level[i]);
    return 0;
}

Python

# 树状数组——AcWing 1265. 数星星
def main():
    N = 32010
    n = int(input())
    tr, level = [0] * N, [0] * n
    # 树状数组范围是x坐标的范围，为N而不是n
    # 级数范围0~n-1
    
    def lowbit(x):
        return x & -x
    
    def add(x, v):
        # 树状数组范围是x坐标的范围，为N而不是n
        while x <= N:
            tr[x] += v
            x += lowbit(x)
            
    def query(x):
        res = 0
        while x > 0:
            res += tr[x]
            x -= lowbit(x)
        return res
    
 	# 转换为树状数组问题的一个关键是定义树状数组的下标和存储含义   
    for _ in range(n):
        x, y = map(int, input().split())
        x += 1 # 注意前缀和存储时一般从1开始，因为整体后移一位
        level[query(x)] += 1
        # 先求级数再插入，防止把自身算入
        add(x, 1)
    print("\n".join(map(str, level)))
    
if __name__ == "__main__":
    main()

AcWing 1215. 小朋友排队

这道题比较困难，一方面考察了对逆序对和冒泡排序的理解，另一方面要真正理解树状数组。

逆序对

设 A 为一个有 n 个数字的有序集 (n>1)，如果存在正整数 i, j 使得$1 ≤ i < j ≤ n$而且$A[i] > A[j]$，则$<A[i], A[j]>$这个有序对称为A的一个逆序对，也称作逆序数。

理解冒泡排序的本质：冒泡排序对相邻两项进行处理，一旦逆序就进行互换。而从整体上看，冒泡排序就是对所有逆序对进行处理，且每次处理一个逆序对，因而冒泡排序的交换次数等于逆序对个数k。

如果只能相邻项交换时，冒泡排序是一种最优的处理方法。每次处理一个，不会有无效操作。因为从贪心的角度，我们只需处理k个逆序对就可以了。

然而我们真的有需要先进行冒泡排序才求解吗？如果这样做就太麻烦了。本实质上完全不需要具体排序。

我们进一步研究，题目要本质上求解的是每个数的交换次数，只要求出次数自然就能求不高兴程度。而对于如何使所有人的不高兴程度之和最小，有两种可能：

本题不满足最优子结构，不能使所有人的不高兴程度同时最小，涉及分配问题
本题满足最优子结构，每个人的交换次数都有一个最小值，且可同时取到，此时只要找到一种方法得出每个人的最小交换次数即可

对于问题的思考显然要从第2个先进行尝试。

而由于冒泡排序就是最优解，我们可以逆向思考，分析冒泡排序中究竟对应哪种情况。可以发现，顺着冒泡排序的思路，只用k次整体就能排好。而具体到每个数，由于不会有多于步骤，在过程中其实只会和自己的逆序对进行交换。换句话说，最优解时每个数的交换次数都是一个固定的最小值且可同时取到。

问题由此就转化为具体每个数对应的逆序对数量。此时我们将其分成两部分，这个数前面比它大的数的个数和这个数后面比它小的数的个数，这和《数星星》这道题就相同了——可以用树状数组边存入边处理，树状数组可以解决求解一个数前面/后面大于/小于它的数的个数。本题分前后分别求解一次即可。（本质是先排序，再求前缀和，排序的过程通过读取时按下标存储解决了）。

边输入边处理

将数字作为下标，如果范围过大需要离散化

// AcWing 1215. 小朋友排队
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 1000010;

int n;
int h[N], tr[N];
int sum[N];

int lowbit(int x){
    return x & -x;// 位运算，返回x最右端一位的1所代表的大小（最后有k个0，则求得值为2^k）
    // 寻找树状数组中的父结点或子结点
}

// 单点修改
void add(int x, int v){
    for (int i = x; i <= N; i += lowbit(i)) tr[i] += v;
    // 树状数组中每个结点i的父节点为i + lowbit(i)
    // 要改变一个结点的值，还要改变其所有祖先节点的值
}

// 区间查询
int query(int x){
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i) scanf("%d", &h[i]), h[i] ++;
    // 注意为了处理前缀和要从1开始存储的问题，把每个值后移一位
 
    // 求每个数前面有多少个数比它大 --> 排序 + 前缀和
    // 边存储（利用下标自动排序）边求解
    for (int i = 0; i < n; ++ i){
        sum[i] = query(N - 1) - query(h[i]);
        add(h[i], 1);
    }

    // 求每个数后面有多少个数比它小 -->排序 + 前缀和
    memset(tr, 0, sizeof tr);
    // 先清空
    for (int i = n - 1; i >= 0; -- i){ 
        // 反向处理
        sum[i] += query(h[i] - 1);
        add(h[i], 1);
    }

    LL res = 0; // 注意会爆int
    for (int i = 0; i < n; ++ i) res += (LL)sum[i] * (sum[i] + 1) / 2;
    // 等差数列公式求和

    cout << res << endl;

    return 0;
}

Python

# 使用数字作为下标
def lowbit(x):
    return x & -x
    
def add(x, v):
    while x <= N:
        tr[x] += v
        x += lowbit(x)
        
def query(x):
    res = 0
    while x > 0:
        res += tr[x]
        x -= lowbit(x)
    return res
        
N = 1000010
n = int(input())
h = list(map(int, input().split()))
h = [0] + [i + 1 for i in h]
sum = [0] * (n + 1)

tr = [0] * N
for i in range(1, n + 1):
    sum[i] += query(N - 1) - query(h[i])
    add(h[i], 1)
tr = [0] * N
for i in range(n, 0, -1):
    sum[i] += query(h[i] - 1)
    add(h[i], 1)
res = 0
for i in range(1, n + 1):
    res += sum[i] *(sum[i] + 1) // 2
print(res)

线段树

树状数组的应用范围完全包含于线段树，且线段树的应用范围要广很多。

线段树是一种基于分治思想的二叉树结构，且除了最后一行其余行都是完全二叉树。用于在区间上进行信息维护和统计。

线段树的结构如下：

线段树的每个节点都代表一个区间
线段树具有唯一的根节点，代表的区间是整个统计范围，如[1, N]，存储整个区间的信息
线段树的每个叶节点都代表一个长度为1的元区间[x, x]
对于每个内部节点$[L, R]$，区间长度不唯一且会进行二分并放到下一层。它的左子节点是$[L, mid]$，右子节点是$[mid + 1, R]$， $，其中mid = \lfloor \frac{L+R}{2} \rfloor$（向下取整）

屏幕截图 2023-03-05 222449

也是维护一个序列，可以进行的操作非常多。

单点修改：修改信息需要变化的相关节点，修改的过程是一个递归+回溯的过程，时间复杂度为 O(logn)
区间查询：也是一个递归的过程，可以求和、最大值、最小值等（取决节点中存啥）。查询时，不断往下递归，知道当前结点范围被带查询区间完全覆盖时停止。时间复杂度为 O(logn)
区间修改：使用懒标记，“延迟更新”

一般数据范围要在$10^5$到$106$能过

节点结构：

线段树需要维护节点信息，节点一般用结构体或类实现。一般维护以下信息：

区间范围：包括左右端点L，R
区间对应的统计信息：由题目决定，包括区间和、区间最大值、区间最小值等

五个核心函数：

pushup:用子节点信息更新当前节点信息(求和、取最大最小值等)
build:在一段区间上初始化线段树

给定一个长度为N的序列A, 我们可以在区间 [1,N]上建立一颗线段树, 每个叶节点[i, i]保存A[i]的值。线段树的二叉树结构, 可以很方便地从下往上传递信息
modify:单点修改单点修改是形如 “C x v” 的指令, 表示把A[x]的值修改为v。在线段树中, 根节点(编号从为1的节点) 是执行各种指令的入口。我们需要从根节点出发, 递归找到代表区间[x,x]的叶节点, 然后从下往上更新[x,x]以及他的所有祖先节点上保存的信息, 时间复杂度为 O(logN)
query:区间查询

区间查询是一条形如"Q l r"的指令, 例如查询序列 A在区间[l,r]上的最大值, 即max(l<=i<=r){A[i]}:我们只需要从根节点开始, 递归执行一下过程:
1. 若[l, r]完全覆盖了当前节点代表的区间, 则立即回溯, 并且该节点的data值为候选答案
2. 若左子节点与[l,r]有重叠部分, 则递归访问左子节点
3. 若右子节点与[l,r]有重叠部分, 则递归访问右子节点
pushdown:懒标记时使用

线段树的总结点数最多为4n，所以要保证线段树的数组长度不小于4N才能保证不会越界。线段树是二叉树，采用数组存储，对于任意结点，其父节点为$\lfloor\frac{x}{2}\rfloor$或x >> 1，左节点为2x或x<<1，右节点为2x+1或x << 1 | 1，使用堆的存储方式

线段树.jpg

AcWing 1264. 动态求连续区间和

C++

// 线段树——AcWing 1264. 动态求连续区间和
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 100010;
int n, m;
int w[N]; // 存储原序列值
// 线段树节点
struct Node{
    int l, r; // 结点所存储的区间范围
    int sum; // 区间的和，根据题意可以维护区间最大值、最小值、和等
}tr[N * 4];
// 注意线段树的总结点数最多为4n，要大于此才能防止越界

// 用左右子节点信息更新当前节点信息
// u为节点编号
void pushup(int u){
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    // 左儿子u << 1 == 2 * u，右儿子u << 1 | 1 == 2 * u + 1(| 1的作用是加1，因为右移后个位一定为0，或1后变为1)

}

// 在一段区间上初始化线段树，递归建立并在回溯时更新信息
// 初始化时传入三个参数：节点编号，左右区间端点；节点编号即为在tr中下标
void build(int u, int l, int r){
    // 边界条件：叶子节点，l==r的原区间
    if (l == r) tr[u] = {l, r, w[r]}; // 叶子节点的值即为原数组对应位置值
    // 区间长度为1，则为叶子结点，直接赋值即可，sum的值为自己本身
    // 注意这里不是w[u]而是w[r]
    else{
    // 区间长度不为1，要进行递归二分
        tr[u] = {l, r};
        // 区间二分，递归赋根节点左右边界初值
        int mid = l + r >> 1; // 区间划分点
        // 初始化左右儿子结点
        // 递归二分处理，直到变为叶子结点
        // 左节点编号2x(x << 1)，区间[l, mid]
        // 右节点编号2x+1(x << 1 | 1)，区间[mid + 1, r]；x << 1后二进制末尾一定是0，此时与1即加1
        build(u << 1, l , mid), build(u << 1 | 1, mid + 1, r);
        // 回溯更新祖先结点
        pushup(u);
    }
}

// 区间查询
// 求和时传三个参数：根结点编号，要查询区间的左右端点
int query(int u, int l, int r){
    // 当前结点已被待求区间完全覆盖，直接返回其值即可
    if (tr[u].l >= l && tr[u].r <= r)
        return tr[u].sum;
    // 当前结点没有被待求区间完全覆盖
    int mid = tr[u].l + tr[u].r >> 1; // 当前区间的中点
    int sum = 0; 
    // l <= mid 说明左子结点区间有交集，递归求解
    if (l <= mid) sum += query(u << 1, l, r);
    // r > mid 说明右子结点区间有交集，递归求解
    if (r > mid) sum += query(u << 1 | 1, l, r);
    // 查询是一个递归的过程，可以求和、最大值、最小值等（取决节点中存啥）
    return sum;
} 

// 单点修改
// 修改时传三个参数：根结点编号，插入的位置，插入的值
void modify(int u, int x, int v){
    if (tr[u].l == tr[u].r) tr[u].sum += v;
    // 叶子节点说明已经找到x的位置，直接修改即可
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        // 求区间中点，深入下一层进行修改，一直要深度到对应子区间
        if (x <= mid) modify(u << 1, x, v); // 左子节点
        else modify(u << 1 | 1, x, v); // 右子节点
        // 修改的过程是一个递归+回溯的过程
        // 需要修改对应子区间及其所有祖先节点
        pushup(u);
        // 注意更新祖先节点
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) scanf("%d", &w[i]);
    // 初始化时传入三个参数：根节点编号，左右区间端点
    // 初始化时把区间范围确定好
    build(1, 1, n);

    int k, a, b;
    while (m --){
        scanf("%d%d%d", &k, &a, &b);
        if (k == 0) printf("%d\n", query(1, a, b));
        // 求和时传三个参数：根结点编号，左右区间端点
        // 节点编号从0开始
        else modify(1, a, b);
        // 修改时传三个参数：根结点编号，插入的位置，插入的值
    }
    return 0;
}

Python

python线段树做法会TLE

# 线段树——AcWing 1264. 动态求连续区间和
class Node:
    def __init__(self):
        self.l, self.r, self.sum = 0, 0, 0
        
def pushup(u):
    """
    :param u: 根节点
    :return: 左右儿子之和
    """
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum

def build(u, l, r):
    """
    :param u: 当前结点编号
    :param l: 左边界（区间左端点）
    :param r: 右边界*（区间右端点）
    """
    # 如果该节点是叶子节点，那就知道它的值为该点的权值，该点编号就是l=r
    if l == r: 、
        tr[u].l, tr[u].r, tr[u].sum = l, r, w[r]
    else:
        # 如果不是叶子节点，那就需要先构造子树
    	# 左二子是u * 2，区间是[l, mid]；右儿子是u * 2 + 1，区间是[mid + 1, r]
    	# 构造好两个儿子后，用两个儿子的sum再求和得到父亲的sum
        tr[u].l, tr[u].r = l, r
        mid = l + r >> 1
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r)
        pushup(u)
        
def query(u, l, r):
    """
    :param u: 根节点编号
    :param l: 查询左端点
    :param r: 查询右端点
    :return: 区间和（返回节点u的区间[tr[u].l, tr[u].r]被区间[l, r]覆盖的数的和）
    """
    # 如果编号为u的节点的左右端点都在[l, r]内，被完全覆盖，那就直接返回该值
    if tr[u].l >= l and tr[u].r <= r:
        return tr[u].sum
    else:
        # 否则返回左二子被该区间覆盖的数的和 + 右儿子被该区间覆盖的数的和
        mid = tr[u].l + tr[u].r >> 1
        sum = 0
        # 如果区间[l, r]和左二子有交点，那就是mid >= r，就要加上左二子被区间[l, r]覆盖的区域和
        if l <= mid: sum += query(u << 1, l, r)
        # 如果区间[l, r]和右二子有交点，那就是r >= mid + 1，就要加上右二子被区间[l, r]覆盖的区域和
        if r > mid: sum += query(u << 1 | 1, l, r)
        return sum
    
# 在编号为u的节点区间[tr[u].l, tr[u].r]中找到i，并修改一系列的值        
def modify(u, x, v):
    """
    :param u: 根节点编号
    :param x: 插入位置
    :param v: 插入的值
    """
    # 该点是叶子节点
    if tr[u].l == tr[u].r:
        tr[u].sum += v
    else:
        # 该点不是叶子节点，如果i在左二子，那就更新左二子，如果i在右儿子中，那就更新右儿子
    	# 然后再用儿子的新sum来更新父节点的新sum
        mid = tr[u].l + tr[u].r >> 1
        if x <= mid:
            modify(u << 1, x, v)
        else:
            modify(u << 1 | 1, x, v)
        pushup(u)
        
n, m = map(int, input().split())
w = [0] * (n + 2)
w[1:] = list(map(int, input().split()))
# 为什么要开4n的区间呢，因为最后叶子节点可能不在一层，即可以理解为多加了一层吧，因为只## 要用到一层，就会用到该层的坐标
# 比如，1~5的区间，只用了9个节点，却不是一颗满二叉树，最后一层有一个叶子节点，所以还是# # 用到了4层，即需要开2**4 = 16个节点
tr = [Node() for i in range(4 * n + 5)]
# 不能写tr = [Node()] * (4 * n + 5)
build(1, 1, n) # 根节点是一号点

for _ in range(m):
    k, a, b = map(int, input().split())
    if not k:
        print(query(1, a, b))
    else:
        modify(1, a, b)

AcWing 1270. 数列区间最大值

C++

// 线段树——AcWing 1270. 数列区间最大值
// 也可使用RMQ，会更快，但不支持修改操作
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <climits>
// INT_MAX int 最大值
// INT_MIN int 最小值

using namespace std;
const int N = 100010;

int n, m;
int w[N];
struct Node{
    int l, r;
    int maxv;
}tr[N * 4];
// 注意线段树的总结点数最多为4n

// 用左右子节点信息更新当前节点信息
void pushup(int u){
    tr[u].maxv = max(tr[u << 1].maxv, tr[u << 1 | 1].maxv);
}

// 在一段区间上初始化线段树
// 初始化时传入三个参数：节点编号，左右区间端点
void build(int u, int l, int r){
    // 边界条件：叶子节点
    if (l == r) tr[u] = {l, r, w[r]};
    // 区间长度为1，则为叶子结点，直接赋值即可，sum的值为自己本身
    // 注意这里不是w[u]而是w[r]
    else{
    // 区间长度不为1，要进行递归二分
        tr[u] = {l, r};
        // 赋根节点左右边界初值
        int mid = l + r >> 1;
        build(u << 1, l , mid), build(u << 1 | 1, mid + 1, r);
        // 初始化左右儿子结点
        // 递归二分处理，直到变为叶子结点
        pushup(u);
        // 回溯更新祖先结点
    }
}

// 区间查询
// 求和时传三个参数：根结点编号，左右区间端点
int query(int u, int l, int r){
    if (tr[u].l >= l && tr[u].r <= r)
    // 当前结点已被待求区间完全覆盖，直接返回其值即可
        return tr[u].maxv;
    // 当前结点没有被待求区间完全覆盖
    int mid = tr[u].l + tr[u].r >> 1;
    // 当前区间的中点
    int maxv = INT_MIN; // 最小值
    if (l <= mid) maxv = max(query(u << 1, l, r), maxv);
    // l <= mid 说明左子结点区间有交集，递归求解
    if (r > mid) maxv = max(query(u << 1 | 1, l, r), maxv);
    // r > mid 说明右子结点区间有交集，递归求解
    // 是一个递归的过程，可以求和、最大值、最小值等（取决节点中存啥）
    return maxv;
}

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n ; ++ i) scanf("%d", &w[i]);
    build(1, 1, n);
    
    int l, r;
    while (m --){
        scanf("%d%d", &l, &r);
        printf("%d\n", query(1, l, r));
    }
    return 0;
}

Python

会TLE

# 线段树——AcWing 1270. 数列区间最大值
# 也可使用RMQ，会更快，但不支持修改操作
class Node():
    def __init__(self):
        self.l, self.r, self.maxv = 0, 0, 0
        
def pushup(u):
    tr[u].maxv = max(tr[u << 1].maxv, tr[u << 1 | 1].maxv)
    
def build(u, l, r):
    if (l == r):
        tr[u].l, tr[u].r, tr[u].maxv = l, r, w[r]
    else:
        tr[u].l, tr[u].r = l, r
        mid = l + r >> 1
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r)
        pushup(u)
        
def query(u, l, r):
    if tr[u].l >= l and tr[u].r <= r:
        return tr[u].maxv
    else:
        mid = tr[u].l + tr[u].r >> 1
        maxv = float('-inf')
        if l <= mid: maxv = query(u << 1, l, r)
        if r > mid: maxv = max(maxv,query(u << 1 | 1, l, r))
        return maxv

n, m = map(int, input().split())
w = [0] + list(map(int, input().split()))
tr = [Node() for _ in range(4 * n + 1)]
build(1, 1, n)

for _ in range(m):
    l, r = map(int, input().split())
    print(query(1, l, r))

类写法

摘自AcWing 1270. 数列区间最大值 - AcWing

# 线段树——AcWing 1270. 数列区间最大值
# 类写法
class treeNode(object): # 子节点
    def __init__(self):
        self.left = -1
        self.right = -1
        self.maxData = -1

class Tree(object):
    def __init__(self, n, data): # 构建线段树
        self.size = n
        self.maxSize = 4 * n
        self.treeNodes = [treeNode() for i in range(self.maxSize + 1)]
        self.data = data

    def pushup(self, cur):
        left_node = self.treeNodes[cur << 1].maxData
        right_node = self.treeNodes[cur << 1 | 1].maxData
        self.treeNodes[cur].maxData = max(left_node, right_node)

    def build(self, cur, left, right):
        # 如果说找到了单独的点，那么直接进行赋值
        if left == right:
            self.treeNodes[cur].left = left
            self.treeNodes[cur].right = right
            self.treeNodes[cur].maxData = self.data[left] # 单独的点的选择
            return
        else: # 说明是找到了一堆点，边界可以确定但是数值不能确定
            self.treeNodes[cur].left = left
            self.treeNodes[cur].right = right

            mid = left + right >> 1
            # 构造左右子树
##            print(cur)
            if mid >= left: # 在if中已经略去了这种情况
                self.build(cur << 1, left, mid)
            if mid + 1 <= right: # 在if中已经略去了这种情况
                self.build(cur << 1 | 1, mid + 1, right) # 可以保证左右子树一定存在吗？
            # 更新父节点的数值, 左右子节点中的较大值
            self.pushup(cur)

    def query(self, cur, left, right):
        if self.treeNodes[cur].left >= left and  self.treeNodes[cur].right <= right:
            return self.treeNodes[cur].maxData
        # print('len(treeNodes), cur', len(self.treeNodes), cur)
        # 为什么下标会超出边界?说明儿子的找法不够正确，不能保证一定会回溯，因此是构造的问题

        # 如果没有完全包含，则查询左右子树
        mid = self.treeNodes[cur].left + self.treeNodes[cur].right >> 1

        maxData = float('-inf')
        # 判断是否需要左子树
        if mid >= left:
            maxData = max(maxData, self.query(cur << 1, left, right))
        if mid + 1 <= right: # 判断是否需要右子树
            maxData = max(maxData, self.query(cur << 1 | 1, left, right))

        # 更新父节点的数值
        return maxData


N, M = map(int, input().split()) # 输入N个数据，查询M个区间
data = [0] * (N + 1)
data[1:] = map(int, input().split())
tree = Tree(N, data)
tree.build(1, 1, N) # 当前节点标号，左边界和右边界
for i in range(M):
    x, y = map(int, input().split())
    res = tree.query(1, x, y) # 从根节点开始询问，从x到y之间的最大值
    print(res)

AcWing 1228. 油漆面积

AcWing 247. 亚特兰蒂斯的简化版，不需要离散化

// AcWing 1228. 油漆面积
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;

int n;
struct Segment{
    int x, y1, y2;
    int k;
    bool operator< (const Segment &t)const
    {
        return x < t.x;
    }
}seg[N * 2];
struct Node{
    int l, r;
    int cnt, len;
}tr[N * 4];

void pushup(int u){
    if (tr[u].cnt > 0) tr[u].len = tr[u].r - tr[u].l + 1;
    else if (tr[u].l == tr[u].r) tr[u].len = 0;
    else tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
}

void build(int u, int l, int r){
    tr[u] = {l, r};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int l, int r, int k)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].cnt += k;
        pushup(u);
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, k);
        if (r > mid) modify(u << 1 | 1, l, r, k);
        pushup(u);
    }
}

int main(){
    scanf("%d", &n);
    int m = 0;
    for (int i = 0; i < n; i ++ ){
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        seg[m ++ ] = {x1, y1, y2, 1};
        seg[m ++ ] = {x2, y1, y2, -1};
    }

    sort(seg, seg + m);

    build(1, 0, 10000);

    int res = 0;
    for (int i = 0; i < m; i ++ ){
        if (i > 0) res += tr[1].len * (seg[i].x - seg[i - 1].x);
        modify(1, seg[i].y1, seg[i].y2 - 1, seg[i].k);
    }

    printf("%d\n", res);

    return 0;
}

扫描线法

类似于积分，使用无限分割思想进行求解。

处理覆盖问题