[算法] 浅讲线段树和树状数组（一）

写在前面

线段树是我最喜欢的数据结构之一了，几乎每一场比赛都能遇到相关的题目，它的强大是有目共睹的。

这篇博客主要是讲讲它的原理及一些应用，顺便提一下线段树的一些应用。

本片博文虽为新手向，但需要你有一定前缀知识，如：

• C++语法基础
• 位运算基础
• 函数的递归和回溯思想
• 分治思想（如二分）
• 基础数据结构（主要为二叉树）

后续还可能会放上讲解可持久化线段树（主席树）的文章（大概

引入 & 建树

对于经常遇见的这样一类问题：

给你$n$个数字（一般是无序序列），接下来再有$m$次操作，每次操作可能是：

• 求某区间的和/最大值/最小值/乘积……
• 修改某个数字/某个区间段里的数字
• ……

其中，$n$和$m$的规模通常在${10}^5$及以上。

刨去修改，如果只有求区间和/乘积，那么使用前缀和计算将是你最好的选择。

如果是求最大值/最小值，也可以使用DP、RMQ、分块等方式解决。

但是一旦加上修改，上述解决方案都不是很适用，而传统暴力做法的时间复杂度将会高达$O(n \cdot m)$。

那么是不是有一种办法可以很好地处理上述问题呢？—— 点我看答案 答案当然是线段树啦！

接下来介绍一下什么是线段树：

线段树是一种二叉搜索树，借助分治算法思想，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个节点。

——改编自百度百科

它的结构大概长成这样（图来源百度百科）：

树中的每一个节点代表一个区间（或者说一条线段）的信息，以二分区间为左右儿子节点，直到不可再分。

不难发现，线段树上的每一个节点，要么没有儿子节点（此区间不可再分），要么必然有两个儿子节点（类似完全二叉树），这为我们建树操作提供了便利。

点我查看线段树结构问题

在早期时笔者一直听有些人说线段树是棵完全二叉树，但实际上并不一定，完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。例如上面百度百科中提到的线段树结构图片就已经可以看出了，这并不是一棵完全二叉树，区间$[6, 6]$和区间$[7, 7]$这两个叶子节点并不在左子树中。

但线段树可以视为一棵平衡二叉树（树中任意节点的左右子树高度差最大为$1$），这是由构成线段树的数据量$n$决定的，由于区间被不断二分，可以考虑类似二分查找的形式，对于叶子节点$p$代表的位置$k$，其在二分查找中至多在$\left\lfloor\log_2{n}\right\rfloor + 1$次会被找到，至少在$\left\lfloor\log_2{n}\right\rfloor$次被找到，所以线段树中的叶子节点之间高度差最大为$1$，也就证明了线段树是一棵平衡二叉树。

若是利用一个一维数组来模拟这棵线段树，将线段树的节点以层序编号，可以发现编号为$p$的节点的两个儿子节点编号分别为$2 \cdot p$和$2 \cdot p + 1$。

再利用递归思想，我们可以先将线段树的叶子节点信息（此时区间必然不可分，只需要存单点的值）保存，解决完某个节点信息时便回溯，此时会回到某个父节点，若其两个儿子节点均已回溯，该父节点的信息便为两个儿子节点信息的合并。

以线段树存储区间和信息为例，这里贴出建树代码：

int a[MAX_N]; // 传入的数组信息
int tree[MAX_N << 2]; // 线段树存储的信息，这里也可以是结构体
void build(int l, int r, int p) {
    // l、r 代表区间，p 代表线段树节点下标
    if (l == r) {
        // 此时区间不可分
        tree[p] = a[l]; // 叶子节点信息
        return ;
    }
    int mid = (l + r) >> 1;
    build(l, mid, p << 1), build(mid + 1, r, p << 1 | 1); // 往左右儿子递归建树
    tree[p] = tree[p << 1] + tree[p << 1 | 1]; // 合并儿子节点信息
}

注：这里没有直接使用乘/除法，而是利用了位运算，属于个人习惯，现代编译器会自动讲乘/除$2^n$转化为位运算方式，读者可自行选择。

这是一个比较粗浅（暴力）的建树方式，也可以以插入节点的方式建树（下文将提及），实际时间复杂度均为$O(n \cdot \log_2n)$，网上还有将线段树结构写成结构体或封装成类的形式，个人建议都要掌握，这里不再详述。

需要注意的两个点：

• 线段树结构的节点数应以大于等于数据量的满二叉树计算（想想为什么？），所以实际申请的空间大致为最大区间长度的$4$倍。
• 若是合并儿子节点信息的操作比较复杂，可以独立成一个函数方便修改，这里只需要相加，所以直接写在建树里。

点我查看建树时间复杂度及空间复杂度分析

关于建树的时间复杂度分析*：

对于数据量恰好可以构成一棵满二叉树，假设叶子节点数（即数据量）为$n$，则其层数为$(\log_2 n) + 1$层，则走到某一叶子节点的时间复杂度是$O(\log_2 n)$。当然在$n$不能表示为形如$2^x$时，其构建出的线段树层数为$\left\lceil\log_2{n}\right\rceil$（或可表示为$\left\lfloor\log_2{n}\right\rfloor + 1$），同样地可以视为每走到一个叶子节点需要的时间复杂度为$O(\log_2{n})$。由于每个叶子节点均需要访问一次，故建树的时间复杂度为$O(n \cdot \log_2 n)$。

关于线段树的空间复杂度分析*：

由上述容易分析线段树叶子节点数为$2^{\left\lceil\log_2{n}\right\rceil}$，根据二叉树性质可以推算出总节点数为$2^{\left\lceil\log_2{n}\right\rceil + 1} - 1$个（含无用节点），易得$2^{\left\lceil\log_2{n}\right\rceil + 1} - 1$与$n$的比值在$n$形如$2^{x} + 1$时取得最大值，带入后计算得$2^{\left\lceil\log_2{n}\right\rceil + 1} - 1 = 2^{x + 2} - 1 = 4 \cdot n - 5$，故实际申请空间大致为数据量$4$倍大小，但可以近似地认为空间复杂度为$O(n)$。

单点修改 & 单点取值

接下来谈谈单点修改，这是线段树中比较简单但很常用的内容。

我们假设现在有$7$个数字组成的数组，将其建成线段树后应为如下结构：

*圆圈内数字为线段树节点的下标

如果我们要修改第$3$个数字的值，那么很容易发现地，只需要找到并修改下标为$10$的这个节点的值，然后不断向上更新，直到根节点。

那么如何找到这个节点？其实很简单，只需要从根节点开始，判断需要查找的位置$k$在当前节点所代表区间$[l, r]$的中点$mid$的左边还是右边，就可以知道接下去要往左儿子走还是右儿子走，直到找到我们想要的节点为止，上面提到的查找/修改路径如下图所示：

推广到一般情况：建树后，无论我们是要修改哪个位置的值，都只需要向下寻找到需要修改的点，然后回溯更新即可。

下面贴上代码（仍以区间和为例）：

void updatePoint(int l, int r, int p, int k, int s) {
    // k为要修改的点位置，s为修改的值
    if (l == r && r == k) {
        tree[p] = s;
    	return ;
    }
    int mid = (l + r) >> 1;
    if (mid >= k) updatePoint(l, mid, p << 1, k, s);
    else if (mid < k) updatePoint(mid + 1, r, p << 1 | 1, k, s);
    tree[p] = tree[p << 1] + tree[p << 1 | 1];
    return ;
}

单点查询与单点修改思想是相同的，即在到达叶子节点时返回这个节点的值，下面贴上代码：

int queryPoint(int l, int r, int p, int k) {
    if (l == r && r == k) {
    	return tree[p];
    }
    int mid = (l + r) >> 1, ret = -1;
    if (mid >= k) ret = queryPoint(l, mid, p << 1, k);
    else if (mid < k) ret = queryPoint(mid + 1, r, p << 1 | 1, k);
    return ret;
}

每次单点修改/查询的时间复杂度均为$O(\log_2 n)$。

点我查看单点/修改查询时间复杂度分析

关于单点修改/单点查询的时间复杂度分析*：

该操作仅会完整地走完树上的一条链，由于线段树是一棵完全二叉树，故其最长链长度与层数相同，为$\left\lfloor\log_2{n}\right\rfloor + 1$（$n$为数据量），所以该操作的单次时间复杂度为$O(\log_2 n)$。

上文建树部分有提到，我们还可以利用单点修改来建立线段树结构，其实就是对于每个数，将其修改（赋值）到对应位置，即对于数组$a$的第$i$个数调用update(1, n, 1, i, a[i])，那么对于$n$个数，总的时间复杂度就是$O(n \cdot \log_2 n)$，与普通建树方式相同（但由于多次重复调用函数，实际常数可能会大些）。

区间查询 & 区间修改

接下来将涉及线段树结构最核心的思想部分。

对于查询某个区间的信息，通过观察可以发现我们只需要访问树上某些节点的信息并合并，而不一定走到叶子节点一个一个地访问（反而有些本末倒置），例如在数据量为$7$且已构建好的线段树中，查询区间$[4,5]$需要访问节点$11$和节点$12$，而查询区间$[3, 6]$只需要访问节点$5$和节点$6$，例如下图所示：

那么，怎么才能知道需要的是哪些节点的信息呢？

对于要询问一个区间$[L, R]$的信息，利用递归思想，从根节点开始，先判断当前访问的节点$p$所拥有的区间$[l, r]$是否完全包含在$[L, R]$中（即$L \leq l \leq r \leq R$），如果是，则这个节点$p$的信息全部需要，否则就判断$p$的两个子树是否有存在$[L, R]$中的信息（即考虑$[l, r]$的中点$mid$与$[L, R]$的关系，若$L \leq mid$，则说明$p$的左子树中有需要的信息，而若$mid < R$，则说明右子树中有需要的信息），然后向下查询，再合并返回查询到的信息。

如模拟在数据量为$7$且已构建好的线段树中查询区间$[3, 6]$信息时，首先是根节点$1$，可以发现此时拥有的节点信息为区间$[1, 7]$的信息，不符合需求，求出此时的中点$mid_1 = (1 + 7) / 2 = 4$，发现$3 \leq mid_1 = 4$，说明节点$1$的左子树（含有$[1, 4]$及其分割区间的所有信息）中有需要的信息，故先前往节点$1$的左子节点$2$。

此时来到节点$2$，拥有的是区间$[1, 4]$的信息，同样不符合我们的的要求，再求出此时的中点$mid_2 = \left\lfloor(1 + 4) / 2 \right\rfloor = 2$，发现$3 > mid_2 = 2$，故节点$2$的左子树（即$[1, 2]$子区间内）无需要的信息，而$mid_2 = 2 < 6$，故节点$2$的右子树中有需要的信息。

然后来到了节点$5$，发现其拥有的区间$[3, 4]$完全包含在$[3, 6]$中，记此处的信息为$ret_1$，这时候返回这个信息，会一路回到根节点$1$，同理可以从根节点$1$的右子树中获得信息，记为$ret_2$，然后合并$ret_1$和$ret_2$（如查询区间和就是$ret_1 + ret_2$）即可得到答案。

将上述过程编写为代码如下（以区间求和为例）：

void querySeg(int l, int r, int p, int L, int R) {
    if (L <= l && r <= R) {
        // 当前区间被查询的区间完全包含
        return tree[p];
    }
    int mid = (l + r) >> 1, ret = 0;
    // 取左子树信息
    if (L <= mid) ret += querySeg(l, mid, p << 1, L, R);
    // 取得右子树信息
    if (mid < R) ret += querySeg(mid + 1, r, p << 1 | 1, L, R);
    return ret;
}

看到这是不是觉得非常简单？读者可以尝试一下证明区间查询的时间复杂度是不是$O(\log_2{n})$。

注：建议先完全掌握区间查询的过程后再学习区间修改。

点我查看区间查询时间复杂度分析

关于区间查询的时间复杂度分析*：

在利用上述过程查找区间$[L, R]$时，我们会碰到一个决策是分析当前节点$p$拥有的区间$[l, r]$的中点$mid$与$[L, R]$的关系，实际上在往左子树查询的时候，就是以$p$的左儿子为根节点的线段树中查询区间$[L, mid]$的信息，由此不断往下搜寻的过程中，$mid$会逐渐往$L$靠拢，根据二分的性质，这个靠拢次数不会超过$\left\lfloor\log_2{n}\right\rfloor + 1$（粗略计算）。

同理，往右子树查询时，就是在查询$[mid + 1, R]$，$mid$也会逐渐往$R$靠拢，这个过程不会超过$\left\lfloor\log_2{n}\right\rfloor$次（粗略计算），故整个查询过程不会超过$2 \cdot \left\lfloor\log_2{n}\right\rfloor + 1$次，那么就可以认为线段树的区间查询的时间复杂度为$O(\log_2{n})$。

当然，在查询的区间长度为$1$时，会一直走到叶子节点（类似单点修改/查询过程），其时间复杂度亦为$O(\log_2{n})$。

注：上述分析过程是笔者较为粗略分析的过程，实际运用中会产生各种常数，可以参考网上关于线段树结构的论文，里面有更详细的时间复杂度证明。

而对于区间修改，则需要引入一个新的概念——懒惰标记（Lazy Tag）。

何谓懒惰标记？其实很简单——就是在要完整修改的区间打上一个标记，说明它被修改过，而此次仅修改该节点的值而不改变其子树的值，即此次修改懒惰不修改，下次经过（有需要修改或查询其子区间时）该点时再将懒惰标记下放到子节点中（同样是修改子节点的值并打上懒惰标记），这样就可以利用到区间查询的思想去找到需要修改的节点。

举个例子：

比如在数据量为$7$且已构建好的线段树中修改区间$[1, 6]$信息时（此前未做任何修改操作），我们利用区间查询思想会先找到第一个需要完全修改的节点为$2$（区间$[1, 4]$），修改其值并加上懒惰标记，然后一路合并到根节点上。同理也会找到另一个需要完全修改的节点$6$（区间$[5, 6]$），重复相同操作。

接下来假设要修改区间$[3, 4]$的值，那么在过程中会先到达节点$2$，但这不是我们要完全修改的区间，需要继续往下，此时发现该节点有懒惰标记，则先下放该标记到两个子节点$4$和$5$中，并清空节点$2$的懒惰标记。

这时候继续向下，发现节点$5$是我们需要完全修改的的区间$[3, 4]$，在此修改值并合并懒惰标记。

最后一路往上合并节点值。

将上述过程编写成代码大致如下（以区间求和、修改操作是对区间所有数加上某个值为例）：

int tree[MAX_N], lazy[MAX_N]; // 节点值与懒惰标记，当lazy[i]为0时代表该节点没有懒惰标记
void pushDown(int l, int r, int p) {
    // 下放懒惰标记操作
    if (lazy[p] != 0) {
        int mid = (l + r) >> 1;
        // 修改子节点值
        tree[p << 1] += (mid - l + 1) * lazy[p];
        tree[p << 1 | 1] += (r - mid) * lazy[p];
        // 合并子节点懒惰标记
        lazy[p << 1] += lazy[p];
        lazy[p << 1 | 1] += layz[p];
        // 清空该节点标记
        layz[p] = 0;
    }
}
void updateSeg(int l, int r, int p, int L, int R, int s) {
    // 区间修改，s代表此区间需要加上的值
    if (L <= l && r <= R) {
        // 修改当前节点值
        tree[p] += (r - l + 1) * s;
        // 合并懒惰标记
        lazy[p] += s;
        return ;
    }
    // 先下放懒惰标记
    pushDown(l, r, p);
    int mid = (l + r) >> 1;
    if (L <= mid) updateSeg(l, mid, p << 1, L, R, s);
    if (mid < R) updateSeg(mid + 1, r, p << 1 | 1, L, R, s);
    tree[p] = tree[p << 1] + tree[p << 1 | 1];
}

注：有带懒惰标记的区间修改中，对于单点修改/查询、区间查询操作也需要先下放懒惰标记再往下查询，此处略去代码。

线段树例题 & 小结

如果你完全掌握了上面讲到的内容，那么可以说明你已经学会线段树的构造和基本使用方法，这边列举几个简单题：

• ZOJ 1610 区间修改模板题（有坑）传送门 Vjudge
• HDU 1166 区间修改模板题 传送门 Vjudge
• HDU 1754 单点修改模板题 传送门 Vjudge
• POJ 3468 区间修改模板题 传送门 Vjudge
• HDU 1698 区间修改模板题 传送门 Vjudge
• CF 438D 线段树单点修改+剪枝，暴力取膜（几乎是模板）传送门 Vjudge
• HDU 4027 区间修改，需要发现开方特性（注意询问区间的l r）传送门 Vjudge

下面再提一道简单的、但看起来不那么像线段树的题目。

例题 - FZU 2297 Number theory

传送门 Vjudge

题目大意

给你一个初始的数字$x = 1$，和一个范围在$[1, {10}^{9}]$数字$M$，有$0 \leq Q \leq {10}^{5}$次操作，每次（或者说第$i$次）操作格式如下：

• M $y_i$ 代表给$x$乘上$y_i$（$1 \leq y_i \leq {10}^{9}$）。
• D $d_i$ 代表让$x$除以$y_{d_i}$。（原题目中这里有错误，操作符是D而不是N）

爆炸每次D操作的$y_{d_i}$是之前乘过的值，要求你输出每次操作后的$x \% M$的值。

题解思路

本题来源为第九届福建省大学生程序设计竞赛，也是笔者参加的第一场ICPC形式的比赛，印象深刻。

初看本题，如果读者学过数论，那么很容易往求逆元的方向思考，但题目给的模数$M$并不一定是一个质数，也不保证$x$在操作后与$M$互质，故本题不能利用逆元求值。

接下来可以发现利用线段树可以算区间乘法的思路来解决这个问题：初始化一棵数据量为$Q$的线段树，叶子节点赋值$1$，这样其根节点的值就是$1$，也就代表了题目$x$。对于每个M操作（假设是第$i$次操作），就是将线段树中区间为$[i, i]$的叶子节点值修改为$y_i$，同理对于每个D操作，就是将区间为$[i, i]$的叶子节点值修改为$1$。由于这个操作仅有单点修改，不需要考虑区间修改时的懒惰标记如何合并/区间值如何修改，故只需要在合并各区间值时取模即可。

每次操作的答案都是线段树的根节点，代码这里就不写了，希望读者可以自己实现。

小结

如果将笔者列举出的线段树例题均独立完成后，相信读者已经对线段树模板有了一定自己的理解，但线段树其实只是个模型（实际上任何算法、数据结构都是），更多的还是需要读者自己思考如何利用线段树解决问题。

关于线段树学习的重点主要就是以下两点：

• 区间查询/修改
• 区间合并

笔者认为对于某些能用线段树解决的题目，这个题目必然满足：支持将数据进行区间二分，并且可以根据二分得到的两个子区间合并得到当前区间的信息（并不一定要支持修改）。

线段树对于解决实际问题并没有太大帮助，在生活中更多地还是利用红黑树或者其他平衡树，但笔者认为学习好线段树是学其他平衡树需要的前缀知识，它相较于其他的平衡树更好实现，在学习的过程中也会把二叉树结构理解得更透彻，并且在算法竞赛中也经常使用。

权值线段树

接下来提一个线段树较为另类的应用。

线段树的变化方式多种多样，这是相对特殊的一种，也可以算是学习可持久化线段树（或者说任何可持久化数据结构）的前缀知识。顾名思义，这棵线段树的节点存的是某种权值，比较常用的是存储区间内各个数字出现的个数（类似桶排序）。

注意：这里提到的区间指的是数值大小而非数据量的区间。

那么有什么用呢？这里举个例题，假设有一个由$n(1 \leq n \leq {10}^{5})$个正整数组成的序列$a (a_i \leq {10}^5)$，要求这个序列中的逆序对数。

这里可以利用单点修改的思想，初始化一颗数据量为$\max(a)$的线段树，其叶子节点存储的值为$0$，也相当于一个空序列中各种数字出现的个数。然后按顺序$i \in 1 \to n$，每访问一个数，先查询线段树区间$[a_i + 1, \max(a)]$的值，我们就得到了序列区间$[1, i]$中大于$a_i$的个数（即在第$i$个数之前有多少个数大于它），假设这个值为$sum_i$，然后再将$a_i$加入到线段树中，最后的答案$ans = \sum_{i=1}^{n} {sum_i}$。

当然，如果$a_i \leq {10}^{9}$甚至更大时，不能直接建立数据量为$\max(a)$的线段树，这里就需要利用离散化或者说映射（例如c++中的map）来缩小数据范围，便可以实现此算法，这里就不展开讲如何离散化了。

这个应用相信读者并不难理解，关键点在于可以利用元素加入线段树的顺序来求得一个$[1,i]$序列中的数字出现个数，或者可以查询某种权值，这点思想在对于之后学习可持久化数据结构（无论何种）时有巨大帮助，仍然希望看到这里的读者好好思考。

这里留一个思考题给笔者：给定由$n(1 \leq n \leq {10}^{5})$个正整数组成的序列$a (a_i \leq {10}^5)$，规定形如$1 \leq i < j < k \leq n$且$a_i < a_j < a_k$为一个三元组，要求你统计序列$a$中三元组的个数。

那么到这里，笔者对于线段树的理解就已经基本讲完了，下一篇将谈谈一些特殊的线段树（如zkw）及树状数组。