正文

rmq类问题利器：线段树(代码片段)

白龙码~  白龙码~  2022-10-23  389

关键词：

文章目录

线段树

线段树

一、问题引入

对于一般的区间问题，比如RMQ(区间的最值)、区间的和，如果使用朴素算法，即通过遍历的方式求取，则时间复杂度为O(N)，在常数次查询的情况下可以接受，但是当区间长度为N，查询次数为M时，查询复杂度就变成O(M*N)。在M和N较大时，这样的复杂度无法满足要求。

对于这类问题，有一个神奇的数据结构，能够在O(M*logN)的时间内解决问题——线段树。

二、线段树的构建

线段树的每个节点可以根据需要存储一个区间的最大/最小值/和等内容。它的构建方式与堆的构建方式类似，即线段树是基于数组实现的树。

以构建区间和的线段树为例：对于给定数组nums，设大小为n，则区间范围为[0, n-1]。

规定线段树的根节点，即SegmentTree[0]存储[0, n)的和。
根据堆的构建方法，父节点的左孩子为2*parent+1，右孩子为2*parent+2。
假设父节点存储[start, end]的和，mid=start+(end - start>>1)，则左孩子存储[start, mid]的和，右孩子存储[mid+1, end]的和

注：mid=start+(end - start>>1)是一种避免整形溢出的写法，等价于mid=(start+end)/2。
由于父节点的值依赖于两个子节点，因此线段树的构建是一种后序遍历。

// nums是给定大小为n的数组，par表示当前正在构建的线段树节点下标，start和end是当前需要计算的区间。
void build(vector<int>& nums, int par, int start, int end)

    if (start == end) // 区间大小为1，即单个点，因此当前节点的区间和就是单点的值
    
        _segmentTree[par] = nums[start];
        return;
    
    // 如果区间大于1，则先求当前节点的左孩子和右孩子
    int mid = start + (end - start >> 1);
    int lchild = 2 * par + 1;
    int rchild = 2 * par + 2;
    build(nums, lchild, start, mid);   // 递归求左节点的区间和
    build(nums, rchild, mid + 1, end); // 递归求右孩子的区间和
    // 当前节点的值就是左孩子的值+右孩子的值
    _segmentTree[par] = _segmentTree[lchild] + _segmentTree[rchild];

注：在极端情况下，最后一层有n个结点，此时线段树是一棵完全二叉树，树的高度h=log₂N向上取整+1≤log₂N+2。

因此，树的节点数量为2^h-1≤2^logN+2-1=4N-1。

所以，线段树数组的大小一般为4*n。

此外，如果想要避免因为n过大而导致MLE，则可以选择map/unordered_map来存储线段树，不过这会增加时间成本。一般来说直接开辟4*n的线段树数组是最方便书写的。

三、线段树的单点修改与查询

1、修改

单点修改要求：修改原数组下标index处的值。此时我们需要对线段树进行更新：

依然是从根节点开始进行修改。
根据修改的下标index，判断应当修改当前节点的左子树还是右子树。
在递归修改左右孩子节点以后，再根据左右孩子的值重新对父节点进行赋值(pushUp())。

void update(int index, int val, int par, int start, int end)

    if (start == end) // 递归结束条件依然是当前区间为单点
    
        segtree[par] = val;
        return;
    
    int mid = start + (end - start >> 1);
    // 递归修改左孩子或右孩子
    if (index <= mid)
        update(index, val, 2 * par + 1, start, mid);
    else
        update(index, val, 2 * par + 2, mid + 1, end);
    // 修改完成后重新对父节点赋值
    pushUp(par);


// pushUp负责利用左右孩子的值更新父节点
void pushUp(int par)

    segtree[par] = segtree[2 * par + 1] + segtree[2 * par + 2];

2、查询

由于每个节点可以存储最值和区间和，因此求最值与求和的过程几乎相同，这里以求和为例：

假设当前节点的区间为[start, end]，中点为mid。
对于给定区间[left, right]，它有三种分布情况：
1. right<=mid，即给定区间全部在左节点中，因此只需要递归左子树计算区间和即可。
2. left>mid，即给定区间全部在右节点中，因此只需要递归右子树计算区间和即可。
3. 给定区间有一部分在左子树，一部分在右子树，因此需要分成两部分，一部分是[left, mid]，这部分到左子树中递归求取。另一部分是[mid+1,right]，这部分到右子树中递归求取。

// [left, right]是目标求和区间，par是当前节点编号，当前节点存储区间[start, end]的和
int query(int left, int right, int par, int start, int end)

    // 目标求和区间与当前节点的区间吻合，直接返回当前节点的值即可
    if (left == start && right == end)
        return segtree[par];
    int mid = start + (end - start >> 1);
    if (right <= mid) // 目标求和区间全部在左子树
        return query(left, right, 2 * par + 1, start, mid);
    else if (left > mid) // 目标求和区间全部在右子树
        return query(left, right, 2 * par + 2, mid + 1, end);
    else  // 目标求和区间分布在左右子树上
        return query(left, mid, 2 * par + 1, start, mid) +
               query(mid + 1, right, 2 * par + 2, mid + 1, end);

四、线段树的区间修改与查询

1、修改

区间修改要求：修改原数组[left, right]处的值，将它们全部加/减value，或者全部改为value。此时我们需要对线段树进行更新。

我们可以选择将[left, right]看成一个个点，然后进行单点修改，但是一个点的修改消耗为log₂N，修改整个区间就是C*log₂N了，M次修改就是M*C*log₂N，这比暴力法的M*C还要差。

我们使用懒标记法，引入一个lazy变量：

依然从根节点开始修改。
如果节点对应的区间[start, end]完全包含在[left, right]中时，即left≤start≤end≤right，此时将这个节点的值进行修改，并按要求修改lazy，比如：对给定区间整体加4，则lazy加4，整体减3，则lazy减3。

修改完lazy数组后，我们不再需要修改它的子节点，因此lazy的意义在于减少向下更新的次数，从而降低时间复杂度**「懒的体现」**。
如果节点对应的区间[start, end]不完全包含在[left, right]中时，则递归修改左右节点，直至对应节点的区间与待修改的区间没有交集**「递归的结束条件」**。子树修改完成后，再利用子节点的值更新父节点(pushUp())。

注意：由于lazy变量的存在，使用子节点的值更新父节点时，需要加上父节点的lazy值，因为该值是由于"偷懒"而没有添加在子节点上的。

// 以「将给定区间内的数加x，查询每个节点存储对应区间的和」为例：
void update(int left, int right, int x, int node, int start, int end)

    // 区间没有交集，无需修改
    if (end < left || right < start)
        return;
    
    // 当前节点对应的区间被需要修改的区间完全包含
    if (left <= start && right >= end)
    
        segtree[node].val += x * (end - start + 1);
        segtree[node].lazy += x;
        return;
    
    
    // 不被[left, right]完全包含，则说明本轮只会更新[start, end]的一部分，因此不能再"偷懒"直接将x加在lazy上了
    // 而是先根据lazy的值修改左右子节点，然后再递归修改左右子树
    int mid = start + ((end - start) >> 1);
    
    // 先利用lazy修改孩子节点
    pushDown(node, mid - start + 1, end - mid);
    
    // 递归修改孩子节点
    update(left, right, 2 * node + 1, start, mid);
    update(left, right, 2 * node + 2, mid + 1, end);
    
    // 利用左右子树的区间最大值确定父节点的区间最大值
    pushUp(par);


void pushUp(int par)

	segtree[par].val = segtree[2 * par + 1] + segtree[2 * par + 2] + segtree[par].lazy;


// par表示父节点，ln表示左孩子的区间长度，rn表示右孩子的区间长度
void pushDown(int par, int ln, int rn)

    if (segtree[par].lazy != 0)
    
        segtree[2 * par + 1].val += segtree[par].lazy * ln; // 修改左孩子的值
        segtree[2 * par + 1].lazy += segtree[par].lazy; // 偷懒，不再往下继续修改，因此左孩子继承父节点的lazy值
        segtree[2 * par + 2].lazy += segtree[par].lazy * rn;
        segtree[2 * par + 2].lazy += segtree[par].lazy;
        segtree[par].lazy = 0; // 父节点的lazy已经分配到子节点了，因此父节点lazy清零

2、查询

查询的过程与修改几乎相同：

依然从根节点开始查询。
如果当前节点有懒标记，此时返回节点的值，无需向下遍历。
当某个节点对应的区间[start, end]完全包含在[left, right]中时，即left≤start≤end≤right，则该节点的值是我们最终结果的子集，直接返回节点值即可。
如果不完全包含，则递归查询左右子树，直至对应节点的区间与待修改的区间没有交集「递归的结束条件」。利用子树的查询结果作为最终的返回结果。

// 以「将给定区间内的数加x，查询每个节点存储对应区间的和」为例：
bool query(int left, int right, int node, int start, int end)

    // 区间没有交集，无需查询
    if (end < left || right < start)
        return false;
    
    // 有懒标记，则无需查询左右孩子，而是直接返回节点值，外加懒标记
    // 或者当前节点对应的区间被需要查询的区间完全包含，则直接返回节点值
    if (segtree[node].lazy || left <= start && right >= end)
        return segtree[node].val;
    
    int mid = start + ((end - start) >> 1);
    // 不完全包含，则先根据lazy修改子节点，再递归查询左右子树的和
    pushDown(node, mid - start + 1, end - mid);  
    
    return query(left, right, 2 * node + 1, start, mid) +
           query(left, right, 2 * node + 2, mid + 1, end);


// par表示父节点，ln表示左孩子的区间长度，rn表示右孩子的区间长度
void pushDown(int par, int ln, int rn)

    if (segtree[par].lazy != 0)
    
        segtree[2 * par + 1].val += segtree[par].lazy * ln; // 修改左孩子的值
        segtree[2 * par + 1].lazy += segtree[par].lazy; // 偷懒，不再往下继续修改，因此左孩子继承父节点的lazy值
        segtree[2 * par + 2].lazy += segtree[par].lazy * rn;
        segtree[2 * par + 2].lazy += segtree[par].lazy;
        segtree[par].lazy = 0; // 父节点的lazy已经分配到子节点了，因此父节点lazy清零

五、算法练习

#rmq，动态开点线段树#cf803gperiodicrmqproblem(代码片段)

RMQ，动态开点线段树题目给定\\(n\\)个数，将这个数列复制\\(k\\)次得到数列\\(a\\)，对\\(a\\)满足区间赋值操作和区间最小值询问\\(n\\leq10^5,q\\leq10^5,k\\leq10^4即|a|\\leq10^9\\)分析先考虑线段树的区间赋值和区间最小值询问，如果没有复... 查看详情

hihocoderweek19rmq问题再临-线段树单点更新区间查询(代码片段)

单点更新区间查询 #include<bits/stdc++.h>usingnamespacestd;#definem((l+r)/2)#definels(rt<<1)#definers(rt<<1|1)constintN=2e6+10;ints[N],tr[N];voidbuild(intrt,intl,intr)if(l==r)tr[rt]=s[ 查看详情

[拆位线段树]rmq(代码片段)

[拆位线段树]RMQ题目https://ac.nowcoder.com/acm/problem/21414思路区间或，区间求和对于区间或，异或这种位运算，没法之间打懒标记。但是如果我们按位拆分，可以发现对于原数组都为01的线段树来说，或运算等效于... 查看详情

蓝书4.1-4.4树状数组rmq问题线段树倍增求lca(代码片段)

这章的数据结构题很真实T1排队bzoj1699题目大意：求静态一些区间的最大值-最小值思路：ST表裸题1#include<iostream>2#include<cstdio>3#include<cstdlib>4#include<cstring>5#include<cmath>6#include<algorithm>7#inc 查看详情

lca欧拉序+rmq(st)欧拉序+rmq(线段树)离线dfs(代码片段)

https://www.luogu.org/problemnew/show/P3379 1.欧拉序+rmq(st) 1/*2在这里，对于一个数，选择最左边的3选择任意一个都可以，[left_index,right_index]，深度都大于等于这个数的深度4*/5#include<cstdio>6#include<cstdlib>7#include< 查看详情

线段树＋rmq问题第二弹

线段树＋RMQ问题第二弹上篇文章讲到了基于SparseTable解决RMQ问题，不知道大家还有没有印象，今天我们会从线段树的方法对RMQ问题再一次讨论。正式介绍今天解决RMQ问题的方法之前，我先对RMQ问题的概念再... 查看详情

rmq_第一弹_sparsetable(代码片段)

...英文便可以看出这个算法的主要是询问一个区间内的最值问题，，，暑假集训的时候学习了线段树，，，也可以对给定数组查询任意区间的最值问题，，，，这两个主要的区别就是线段树可以查看详情

一码学程10284排队找bug题解单调队列或者线段树rmq(代码片段)

...目，未评测，所以不确定代码正确性，但是算法思路没有问题描述同学们的bug还真是多啊，orz...春节期间大家存下的bug都来找肖老师解决了。每个人都有bug，但是肖老师却只有一个啊。怎么办？所以肖老师让大家按先来后到的顺... 查看详情

poj-3264rmq(代码片段)

...内最值之差。数据太大，暴力是行不通的，首先想到的是线段树，但RMQ实行和理解起来更简洁，就以新学的算法来写啦，所以等下细记录RMQ代码，略记录线段树代码，反正我的博客我做主，也就我查看详情

51nod.1766.树上最远点对(树的直径rmq线段树/st表)(代码片段)

题目链接(Description)给定一棵树。每次询问给定(asimb,csimd)两个下标区间，从这两个区间中各取一个点，使得这两个点距离最远。输出最远距离。(n,qleq10^5)。(Solution)一个集合直径的两端点，在被划分为两个集合后一定是两个集合直... 查看详情

[luogup1816]忠诚（rmq||线段树）

传送门其实我就是想练练rmq本以为学了线段树可以省点事不学rmq了但是后缀数组中用rmq貌似很方便所以还是学了吧，反正也不难 ——代码1#include<cstdio>2#defineN1000013#definemin(x,y)((x)<(y)?(x):(y))45intn,m;6inta[N],d[N][21]... 查看详情

rmq算法(代码片段)

定义RMQ(RangeMinimum/MaximumQuery)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。简介主要方法及复杂度如下：1、朴素（即搜索），O... 查看详情

uva12299带循环移动的rmq（线段树）

...区间最值。现在要循环移动（往前移动）。分析：求区间问题，很容易想到线段树，西东就相当于单点更新。建树，有两种方案，第一种是nlogn，就是不断的更新，更新logn，有n个数。1#include<bits/stdc++.h>23usingnamespace 查看详情

rmq一点感悟(代码片段)

...mum Query)【区间最值】主要是这两种算法解决区间最值问题：线段树和稀疏表(SparseTable)ST算法是解决RMQ（区间最值）问题，它能在O（nlogn）的时间预处理，然后O（1）回答。其原理是倍增，f[i][j]表示从i位起的2^j个数中的最大... 查看详情

线段树（segmenttree）(代码片段)

　　线段树是一种二叉搜索树，它的每一个结点对应着一个区间[L,R]，叶子结点对应的区间就是一个单位区间，即L==R。对于一个非叶子结点[L,R]，它的左儿子所表示的区间是[L,(L+R)/2]，右儿子所代表的的区间是[(L+R)/2+1,R]。　　拿... 查看详情

rmq问题st算法(代码片段)

RMQ是询问某个区间的最大值或最小值的问题，主要求解方法之一ST算法；ST算法其实是倍增思想的产物,等下看代码实现就很明显了ST算法通常用在要多次询问一些区间的最值的问题中，相比于线段树，它的程序实现更简单，运行... 查看详情

uva11235frequentvalues线段树/rmq

　　vjudge上题目链接：UVA11235*******************************************************大白书上解释************************************************************　　题目大意：给出一个非降序排列的整数数组a1,a2,a3,...,an，你的任务是对于一系列询问(i,j)，回... 查看详情

数据结构——线段树(代码片段)

前置知识二叉树正篇首先先来一个问题：给出一个长度为n的序列和m个操作，操作分别是:单点修改单点查询区间加减区间查询和模板题出处最简单的做法就是在数组上暴力for,这样的话单点修改和查询的时间复杂度是(O(1)),区间加... 查看详情

正文

rmq类问题利器：线段树(代码片段)

文章目录

线段树

一、问题引入

二、线段树的构建

三、线段树的单点修改与查询

1、修改

2、查询

四、线段树的区间修改与查询

1、修改

2、查询

五、算法练习

LeetCode 307 单点修改问题

LeetCode 732 区间修改问题

#rmq，动态开点线段树#cf803gperiodicrmqproblem(代码片段)

hihocoderweek19rmq问题再临-线段树单点更新区间查询(代码片段)

[拆位线段树]rmq(代码片段)

蓝书4.1-4.4树状数组rmq问题线段树倍增求lca(代码片段)

lca欧拉序+rmq(st)欧拉序+rmq(线段树)离线dfs(代码片段)

线段树＋rmq问题第二弹

rmq_第一弹_sparsetable(代码片段)

一码学程10284排队找bug题解单调队列或者线段树rmq(代码片段)

poj-3264rmq(代码片段)

51nod.1766.树上最远点对(树的直径rmq线段树/st表)(代码片段)

[luogup1816]忠诚（rmq||线段树）

rmq算法(代码片段)

uva12299带循环移动的rmq（线段树）

rmq一点感悟(代码片段)

线段树（segmenttree）(代码片段)

rmq问题st算法(代码片段)

uva11235frequentvalues线段树/rmq

数据结构——线段树(代码片段)