高级数据结构(1)-线段树

2020-07-01 本文已影响0人西部小笼包

这应该是系统介绍LC的线段树题目全网截止发文时最全的文章了。
从这篇文章里，你可以学到如何用线段树思维和模板解LC的超难题。
这篇文章算是进阶文章，不适合完全不知道线段树是什么的，以及最基本的操作为什么可以这么写的小伙伴。
关于基础，网上有很多资料。
你会收获的知识点如下：

普通基于数组的线段树和动态开点的线段树，及各自的运用场景与优劣势
线段树可以为我们做什么，如何站在巨人（线段树）的肩膀上思考问题
如果快速套模板去攻破Leetcode的所有的线段树问题

---------------------2020.7.5 更新--------------------------------

今天又多了一道线段树的题目。

1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits

这道题按照1353. Maximum Number of Events That Can Be Attended的思路，我们可以开10个桶，存下标。然后就根据K的大小去看， 0里面的最前的下标能否够换。如果不行，后面的0的下标也就不用看了，最小的都不够换。那只能取试试1的。
想到这步后面有个棘手的问题就是，我们摆了一个位置后（换过去之后）这个位置前的所有数的原下标都要++。
比如[3,1,0] 我们把0 放到最前面。3的下标从0变到1， 1的下标从1变到2.
所以等价于我们把0下标之前的所有下标都要+1。这步又是O(N)的。
这是一个区间更新，我们就可以想到线段树。我们让线段树每个叶子节点存的是当前这个原始下标需要向右偏移多少位。
这样我们下次去查的时候，比如这时最前面的是下标是2，我们要去线段树2这个叶子节点上读取偏移量才是他目前真正的下标。然后再看移动的距离和K比够不够。
主函数代码

public String minInteger(String num, int k) {
        // 预处理10个桶的下标
        Queue<Integer>[] m = new Queue[10];
        for (int i = 0; i < 10; i++) m[i] = new LinkedList<>();
        char[] cs = num.toCharArray();
        for (int i = 0; i < cs.length; i++) m[cs[i] - '0'].offer(i);
        
        // 初始化线段树
        char[] res = new char[cs.length];
        int idx = 0;
        tr = new Node[4 * cs.length];
        build(1, 0, cs.length);
        // 开始构建 res
        while (idx < cs.length) {
            for (char c = '0'; c <= '9'; c++) {
                Queue<Integer> q = m[c - '0'];
                if (q.isEmpty()) continue;
                // 找到下标
                int cur = q.peek();
                // 搜索CUR这个叶子节点的偏移量
                cur += query(1, cur, cur);
                if (k < cur - idx) continue;
                k -= cur - idx;
                res[idx++] = c;
                int pos = q.poll();
                // 更新区间[0, POS] 所有的偏移量+1
                update(1, 0, pos, 1);
                break;
            }
        }
        return new String(res);
    }

然后就是修改线段树的模板（模板用法，请先读下面的文章）

image.png

线段树的基本思想

https://oi-wiki.org/ds/seg/
线段树的基本思想可以直接看这个WIKI。
然后一般线段树会开一个4倍于要维护区间的数组。比如要维护的区间是[11,20] ；就会用长度为40的数组。然后数组下标是1 是根节点，表示的范围是[11, 20]， 任何一个节点的左孩子是 2 * i, 右孩子是2 * i + 1.
当然是和i << 1 和（i << 1）|1等价。
数组式线段树，一般会有3个接口函数

BUILD（根据初始ARRAY，或者直接构建初始线段树，作用就是给NODE 赋予初始值）
query （从哪个节点下标开始，取[L, R]的范围的值）
update (从哪个节点下标开始，用VAL 更新[L, R]的区间）

因为区间更新可以兼容单点更新，所以我放模板的时候统一用区间更新，如果遇到一道题只需要单点更新，那么可以无视PUSH DOWN 函数，以及把L, R传成一个数即可。

上面3个接口函数，都是递归套路的写法。

另外决定每个线段树不一样的性质是VAL的定义。我们都知道每个NODE里会维护一个VAL。这个VAL可以有不同的解释，那么在对应的区间可加性上就会有不同的算法。

所谓区间可加性是线段树使用的一个必要条件。比如我们要维护[1,10]的区间和。我们知道的是[1,5] 和 [6,10]的区间和，我们怎么根据2个子区间的信息构造全局区间的信息，如果可以做到，就满足区间可加性。同时很重要的一点是，如果我们的题目要用到范围更新，那么懒标记也要满足区间可加。比如我们要求区间的最大公约数，这个是区间可加的，但是更新区间的时候，是在原范围内的所有数都加上一个值，这就会引起最大公约数和这个DELTA的增量不可加的情况，这个时候，我们得优化算法使得其变成区间可加。会比较难。

然后线段树在维护节点的时候，和数据结构里的堆非常类似，会需要自定义2个基本操作。一个叫PUSHUP，他的含义就是根据孩子信息更新父亲信息。
另外一个在涉及到需要用到区间更新，懒标记的时候才需要的函数，叫PUSHDOWN，他的含义是用父亲的懒标记，更新还在的信息和懒标记

所以在用线段树的模板时，基本只要考虑3个问题，

每个节点的VAL定义是什么
如何更新VAL（包含如何PUSHUP）
是否有区间更新 , 如果有，如何定义懒标记，和PUSHDOWN

下面我给出普通线段树的模板，然后会介绍模板如何使用

class Node {
    int rgLeft, rgRight; // 该节点负责的左区间和右区间。前闭后闭
    int sign; // 延迟懒标记，用于区间更新
    int val; // 节点的VAL值，不同题目下含义不同
    public Node(int left, int right) {
        this.rgLeft = left; this.rgRight = right;
    }
}
Node[] tr;
// pushup 就是利用孩子的信息更新父亲的信息 (u << 1) 为左孩子， （u<<1|1)为右孩子
void pushup(int u) {
    Node left = tr[u << 1], right = tr[u << 1 | 1];
    tr[u].val = merge(left.val, right.val);
}
// 把2个子区间的VAL，利用线段树的区间可加性，归并到总区间的VAL
private int merge(int left, int right) {
    // TODO
    return -1;
}
// 根据父亲的懒标记，去更新孩子的VAL及懒标记
void pushdown(int u) {
    if (tr[u].rgLeft != tr[u].rgRight) {
        // get sign
        // use sign update rgLeft child val and rgLeft sign
        // use sign update rgRight child val and rgRight sign
    }
    // clear sign
}
// 线段树初始化函数， u 代表当前节点的INDEX， L代表负责的左区间，R代表负责的右区间
void build(int u, int l, int r) {
    if (l > r) return;
    if (l == r) {
        tr[u] = new Node(l, l);
    } else {
        tr[u] = new Node(l, r);
        int mid = (l + r) / 2;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
// 线段树区间查询函数， u 代表当前节点的INDEX， L代表query的左区间，R代表query的右区间
int query(int u, int l, int r) {
    if (l > r) return 0;
    if (tr[u].rgLeft >= l && tr[u].rgRight <= r) return tr[u].val;
    else {
        pushdown(u);
        int mid = (tr[u].rgLeft + tr[u].rgRight) >> 1;
        if (r <= mid) return query(u << 1, l, r);
        else if (l > mid) return query(u << 1 | 1, l, r);
        return merge(query(u << 1, l, r), query(u << 1 | 1, l, r));
    }
}
// 线段树区间更新函数， u 代表当前节点的INDEX， L代表要更新的左区间，R代表要更新的右区间， VAL是要更新的值
void update(int u, int l, int r, int val) {
    if (tr[u].rgLeft >= l && tr[u].rgRight <= r) {
        // update val
        // TODO : update sign?
    } else {
        pushdown(u);
        int mid = (tr[u].rgLeft + tr[u].rgRight) >> 1;
        if (l <= mid) update(u << 1, l, r, val);
        if (r >= mid + 1) update(u << 1 | 1, l, r, val);
        pushup(u);
    }
}

我们来看一道入门线段树的题目
是LEETCODE 307 题

307. Range Sum Query - Mutable

在这道题中，我们首先思考他是在对区间的一个点做变化，同时要快速求得区间和。那么就可以想到线段树。

所以第一步就是想到可以用线段树

第二步就是想这题中每个NODE节点里的VAL 的定义是什么

在这题里很好想，这要维护区间和就可以。那么VAL就是这个NODE所表示的区间的区间和。

第三步
想到要用线段树之后,如何更新，题目中说的是把一个值更新到另一个值，那么因为是维护区间和，所以MERGE函数就是LEFT + RIGHT

所以我们要写的就这么2行代码

image.png

因为用不到区间更新，所以我们可以直接无视PUSHDOWN函数

第四步
就是如何站在线段树这个数据结构上去解决原问题。
那么其实原问题要做的事情都和线段树的接口函数一一对应了。
所以直接调用即可。

image.png

离散化和动态开点

因为线段树开初始空间的情况完全依赖与最小和最大的区间范围。
比如我们有一些操作，里面数的最小值可能会达到Integer.MIN_VALUE , 数的最大值可能会达到Integer.MAX_VALUE
但是数的量大概只有10000~100000左右。那么为了这么一点数去开2^32这么大的空间是不现实的。会直接暴内存。

这个时候，就有2种做法。第一种做法就是预处理数据，把原来分散点的集中起来。比如[100, 2000, 9000, 100000000] 这4个点，我们把它变成[1,2,3,4] 同时利用一个MAP我们可以查询100 对应的是线段树里的1. 线段树里的1 可以查出是原数组里的100.
那么我们不离散化需要开4 * [100, 100000000] 这么大区间的线段树数组。离散化后，因为只有4个数，其实只要开 4 * [1, 4]，也就16大小的数组即可了。

离散化的优点就是，可以使得空间更加紧凑，并且用了离散化后可以使用数组来存线段树的节点，效率更加高。

缺点就是要写更多的代码去对原数据做预处理，然后再使用线段树接口函数的时候，也要把输入用预处理的MAP做个转换。有时可能输出也要做个转换回原数据。

上面这个缺点只是对程序员来说，需要花更多的力气。（懒人创造时间，LESS IS MORE）但是如果为了追求性能，是可以采用的。但是还有另外一个致命的缺点。

就是你这个程序如果要用离散化开线段树，你必须一开始就要知道全量的数据，这样你才能根据这些数据，排出顺序，知道需要多少空间。

比如我们现在要提供这样一个数据结构，可以随时INSERT 一个区间。也就是我们常说的流处理，或者在线处理。这个时候我们一开始是没有全量信息的。我们就只能使用动态开点的方式。

动态开点线段树

所谓动态开点的含义就是，一开始只有一个根节点，他代表了你这个程序所支持的输入可能的数据范围。然后你需要更新或者查找哪个区间，我按需在帮你把这些区间涉及到的内部节点给创造出来（如果调用的时候没有的话）。

这种方式的优点有2个。

可以处理在线数据
不用预处理数据了，直接使用即可。

缺点是

空间会是n log n，原来数组法是O（n），这里的N是多少个数（在之前的例子里是4，在在线的例子里是INSERT的次数），这个多出来的空间一般也不影响解题
节点使用指针相连，没法利用数组有的缓存局部性，时间上常数也会比数组的要大。但是这个常数一般不影响做题。

下面给出动态开点线段树的模板

class Node {
    long rgLeft, rgRight;
    private Node left, right; // 不要直接用左孩子， 右孩子， 用对应方法去拿
    int val;
    public Node(int start, int end) {
        rgLeft = start;
        rgRight = end;
    }
    public int getRangeMid() {
        return (int) (rgLeft + (rgRight - rgLeft) / 2);
    }
    // 返回左孩子，如果不存在就动态创建
    public Node left() {
        if (left == null) left = new Node((int)rgLeft, getRangeMid());
        return left;
    }
    // 返回右孩子，如果不存在就动态创建
    public Node right() {
        if (right == null) right = new Node(getRangeMid() + 1, (int)rgRight);
        return right;
    }
}
// 线段树初始化函数， cur 是当前节点， L代表查询的左区间，R代表查询的右区间
int query(Node cur, long l, long r) {
    if (l > r) return 0;
    if (cur.rgLeft >= l && cur.rgRight <= r) return cur.val;
    else {
        pushdown(cur);
        long mid = (cur.rgLeft + cur.rgRight) >> 1;
        if (r <= mid) return query(cur.left(), l, r);
        else if (l > mid) return query(cur.right(), l, r);
        return merge(query(cur.left(), l, r), query(cur.right(), l, r));
    }
}
// 根据父亲的懒标记，去更新孩子的VAL及懒标记
void update(Node cur, int l, int r, int val) {
    if (cur.rgLeft >= l && cur.rgRight <= r) {
        // update val
        // TODO : update sign?
    } else {
        pushdown(cur);
        long mid = (cur.rgLeft + cur.rgRight) >> 1;
        if (l <= mid) update(cur.left(), l, r, val);
        if (r >= mid + 1) update(cur.right(), l, r, val);
        pushup(cur);
    }
}
void pushup(Node cur) {
    cur.val = merge(cur.left().val, cur.right().val);
}
private int merge(int left, int right) {
    return -1;
}
void pushdown(Node cur) {
    if (cur.rgLeft != cur.rgRight) {
        // get sign
        // use sign update rgLeft child val and rgLeft sign
        // use sign update rgRight child val and rgRight sign
    }
    // clear sign
}

到这里线段树的模板基本介绍完了。

我们就根据每道题的特质，来选取线段树最便捷的策略，开始A题之旅。

常见线段树CASE1-维护区间个数

这类线段树，又被称之为权值线段树。或者说桶线段树。比如我们有这样一个数组[1,1,2,2,4,4,8,8,8]
如果我们要找第K小的，我们可以先把上面的元素都放进桶里，然后2分。每个桶里存的是数值为1的数的个数有几个，数值为2的数的个数有几个，以此类推。然后对这些桶的值求一个PRESUM（前缀和数组），之后就可以在这个数组上2分找到第K小。
那么按照这个思路，其实PRESUM就是在做区间查询，查询的是这个区间所管辖的数值的做个数。
那么第一步就可以想到用线段树。
而更新操作其实就是给一个叶子区间（桶）做一个CNT++的。所以是单点更新。同时PUSHUP，就是leftCnt + rightCnt 就是父亲的cnt

493. Reverse Pairs

比如leetcode 493题，他是要求逆序对的数量，这里的逆序对if i < j and nums[i] > 2*nums[j].
下面就是如何站在线段树的肩膀上思考问题。
因为我们是从前往后插入线段树，对于每一个当前的数，其实它对应的下标更大所以是J，线段树里的都是比他小的下标所以是I。那么对于J来说，只要在之前的桶里找到比自己的数值2倍还要大的区间的总个数，就是能和自己组成所有逆序对的个数。
因为这道题数据范围给的是INT全集，并且是离线的操作，所以我们可以使用离散化，当然也可以动态开点。下面给出动态开点，我们需要填写的代码。
注意因为输入就是INT全集了，所以2倍为了防止整型溢出，需要转成long。我的QUERY模板里，是支持LONG的QUERY，但是根节点的范围用的是INT，也就是最多只能覆盖INT全集而不是LONG全集

image.png
关于线段树本身，模板也只要写2行，因为只涉及单点修改，所以可以无视pushdown()

image.png

315. Count of Smaller Numbers After Self

315 这个也是一个同样的问题，只不过他要找的是后面比他小的个数。那么我们就可以维护权值线段树，然后从后往前处理。找到从[MIN, 自己VAL-1]区间的CNT，即可

image.png

和上面那道题的代码几乎差不多，而且站在线段树的肩膀上，逻辑也非常好想和好写。

327. Count of Range Sum

我们在看327题，这道不是要找简单的大或小的范围了。他要求了一个容错的区间[lower, upper]，并且他是在统计区间和的容错区间的个数。
这道题因为要求的是个数，还是要基于权值线段树。然后又要维护一个和的范围，那么就可以想到要用前缀和数组。
另外这里的输入是INT全集，还要再全集上求前缀和，势必要用到LONG。那么范围过大了（如果开LONG的动态开点，LOG的代价会到64，而且LONG的边界不好处理），这里使用了离散化的方式。
所以这道题就是对前缀和从前往后遍历。后面的前缀和，需要找到2个端点[low,up]的区间，使得presum[i] - low <= upper and presum[i] - up >= lower
然后用这个区间，去在线段树里找有多少个PRESUM 是符合条件的。

image.png
线段树本身的模板还是只要改那2行。所以不展示出来了。

406. Queue Reconstruction by Height

406这一题，一般面试是要求你用O(n^2)的解法去做就可以了。
但是这道题最优的做法是O(nlogn)。其实也有多种做法，比如分治就可以解。分治的解法，我会另开专题去讲。这里就讲下如何用权值线段树去解。
首先我们要分析出一个性质。把所有元素按第一位从小到大排序，如果第一位相等，第二位大的在前面。这样的数有一个性质。
因为第一位是当前最小，那么如果第二位是K个，那么他在放进队伍中的时候，前面只要留K个空位置（因为之后的数都至少>=它，只要后面的数放进他留的K个空位，必定满足题目性质）
所以这道题，就是需要动态去找这个数组已经用掉的位置不算，在余下的没用掉的位置里，第K个位置是全数组的第几个下标。
然后每个元素就一次用元素的第二位去查这个信息，就知道自己该放到哪了。
比如说一开始一共有8个数要排队。那么我们就开一个线段树[0,7]的线段树，VAL 就表示成这个区间可用位置的个数。然后没放进一个元素，我们单点更新VAL=0，这样可用位置就会少1.
我们在查找第K大的可用位置，只要先去看左半区间的总的可用位置个数是否>K，如果大，我们就去左半区间找。如果小，我们就去右半区间找第（k-左半区间的总的可用位置个数）大的可用位置即可。
因为这题只需要单点query和update,所以我把2个函数合并为一个简化版的函数。其他地方还是原模板的写法

image.png

常见线段树CASE2-维护区间最值

线段树另一类常见操作就是维护区间最值，最值也有区间可加性。
我们从一道题开始

732. My Calendar III

这道题要求返回的是加上一个EVENT之后，最多的重叠层数。那么我们就可以维护区间里，最多的重叠层数即可。比如左半区间最多重叠层数是2，右半区间是4，那么总区间就是这2个的最大值。
更新的时候，只要更新对应区间里的值使他们val+1即可，表示我们又在这个区间盖上一层。（这里就好比给区间盖被子，找到区间里被子最厚的地方）
另外这道题就是我们说的在线操作，一开始无法知道所有的输入，不知道客户端未来会输入什么范围，而且输入是10^9,所以只能用动态开点。
如果你们已经走过上面的每一道题，应该对模板已经用的比较熟练了，除了pushdown，那这里就带大家练习pushdown

image.png
SIGN 的含义就是我这层还没给孩子透传的要加的DELTA是多少。若果需要PUSHDOWN了，我就把DELTA加到孩子上，同时加到孩子SIGN上，当他们需要更新他们的孩子时，他们也要拿着自己的SIGN去做这件事（当然是延迟告诉的，只要需要的时候才会用到SIGN去更新）

image.png
最后就是用线段树接口函数去写题目就非常简单了， 4行代码

image.png

699. Falling Squares

这道题本质上和前一道题差不多，也是盖被子，然后被子的厚度是不同的（之前那道题被子厚度全是1）。另外一个问题这个被子是刚性的，也就是说如果中间比较厚两边比较薄，被子不会像现实中可以贴合的覆盖上，而是以最厚的那部分为接触点，钢板被子硬邦邦的叠在上面。
所以我们不能直接给区间每个点+上厚度。需要先把要覆盖的区间的最大厚度找出来，然后加上自己的厚度。然后用这个厚度去更新所有要覆盖的区间。这里的更新是直接赋值，而不是累加。

我们可以看到用了线段树之后，主代码都非常好写好想。把原来复杂的问题简化了很多。

image.png

218. The Skyline Problem

这道题也是差不多。拿到一个楼，就拿这个楼的天花板去更新他所管辖区间的天花板最高值。所以这里的更新，如果比它高才更新。更新的时候也需要用MAX操作。
那么所有楼做了这个操作后，线段树就维护出了天际线的天花板。我们需要用每一个楼可能的横坐标（楼的最左侧和最右侧），去对所有横坐标排序，然后依次遍历这个坐标的高度，是否发生了变化。就能拿把题目的输出给构建出来。

public List<List<Integer>> getSkyline(int[][] buildings) {
    TreeSet<Integer> t = new TreeSet<>();
    // 存储所有楼的可能涉及到的横坐标
    for (int[] b : buildings) {t.add(b[0]); t.add(b[1]);}
    if (t.isEmpty()) return new ArrayList<>();
    // 利用最小最大横坐标，构建线段树根节点
    Node root = new Node(t.first(), t.last());
    // 用天花板高度去更新最大高度
    for (int[] b : buildings) update(root, b[0], b[1]-1, b[2]);
    int preH = 0, prex = t.first();
    List<List<Integer>> res = new ArrayList<>();
    // 依次遍历每个坐标，如果高度发生变化就加到结果集中
    for (int x : t) {
        int h = query(root, prex, x-1);
        if (h != preH) res.add(Arrays.asList(prex, h));
        prex = x;
        preH = h;
    }
    // 结尾归0的点加进结果集里
    res.add(Arrays.asList(prex, 0));
    return res;
}
class Node {
    long rgLeft, rgRight;
    Node left, right;
    int val, sign;
    public Node(int start, int end) {
        rgLeft = start;
        rgRight = end;
    }
    public int getRangeMid() {
        return (int) (rgLeft + (rgRight - rgLeft) / 2);
    }
    public Node left() {
        if (left == null) left = new Node((int)rgLeft, getRangeMid());
        return left;
    }
    public Node right() {
        if (right == null) right = new Node(getRangeMid() + 1, (int)rgRight);
        return right;
    }
}
int query(Node cur, long l, long r) {
    if (l > r) return 0;
    if (cur.rgLeft >= l && cur.rgRight <= r) return cur.val;
    else {
        pushdown(cur);
        long mid = (cur.rgLeft + cur.rgRight) >> 1;
        if (r <= mid) return query(cur.left(), l, r);
        else if (l > mid) return query(cur.right(), l, r);
        return merge(query(cur.left(), l, r), query(cur.right(), l, r));
    }
}
void update(Node cur, int l, int r, int val) {
    if (cur.rgLeft >= l && cur.rgRight <= r) {
        // update val
        cur.val = Math.max(cur.val, val);
        // TODO : update sign?
        cur.sign = Math.max(cur.sign, val);
    } else {
        pushdown(cur);
        long mid = (cur.rgLeft + cur.rgRight) >> 1;
        if (l <= mid) update(cur.left(), l, r, val);
        if (r >= mid + 1) update(cur.right(), l, r, val);
        pushup(cur);
    }
}
void pushup(Node cur) {
    cur.val = merge(cur.left().val, cur.right().val);
}
private int merge(int left, int right) {
    return Math.max(left, right);
}
void pushdown(Node cur) {
    int sign = cur.sign;
    if (cur.rgLeft != cur.rgRight) {
        // get sign
        // use sign update rgLeft child val and rgLeft sign
        cur.left().val = Math.max(cur.left().val, sign);
        cur.left().sign = Math.max(cur.left().sign, sign);
        // use sign update rgRight child val and rgRight sign
        cur.right().val = Math.max(cur.right().val, sign);
        cur.right().sign = Math.max(cur.right().sign, sign);
    }
    cur.sign = 0;
    // clear sign
}

其他线段树CASE

715. Range Module

这道题是在维护区间存在性，也就是说这个区间要么存在，要么不在，所以不是1就是0. 如果已经是1了，你再add也还是1. 如果已经是0了，你再remove也还是0
所以add时val传1， remove时val传0。然后线段树更新的时候就直接赋值即可。
区间的VAL表示总区间是否全部存在（因为query是看query的区间是否全部存在），所以就是左子树和右子树都为1，才是1. 只要有0，就是0. 那么更新的时候用 max即可。

class RangeModule {
    Node root = new Node(0, (int) 1e9);
    public RangeModule() {
        
    }
    public void addRange(int left, int right) {
        update(root, left, right-1, 1);
    }
    
    public boolean queryRange(int left, int right) {
        return query(root, left, right - 1) == 1;
    }
    
    public void removeRange(int left, int right) {
        update(root, left, right-1, 0);
    }
    
    class Node {
        long rgLeft, rgRight;
        Node left, right;
        int val;
        int sign;
        public Node(int start, int end) {
            rgLeft = start;
            rgRight = end;
            sign = -1;
        }
        public int getRangeMid() {
            return (int) (rgLeft + (rgRight - rgLeft) / 2);
        }
        public Node left() {
            if (left == null) left = new Node((int)rgLeft, getRangeMid());
            return left;
        }
        public Node right() {
            if (right == null) right = new Node(getRangeMid() + 1, (int)rgRight);
            return right;
        }
    }
    int query(Node cur, long l, long r) {
        if (l > r) return 0;
        if (cur.rgLeft >= l && cur.rgRight <= r) return cur.val;
        else {
            pushdown(cur);
            long mid = (cur.rgLeft + cur.rgRight) >> 1;
            if (r <= mid) return query(cur.left(), l, r);
            else if (l > mid) return query(cur.right(), l, r);
            return merge(query(cur.left(), l, r), query(cur.right(), l, r));
        }
    }
    void update(Node cur, int l, int r, int val) {
        if (cur.rgLeft >= l && cur.rgRight <= r) {
            cur.val = val;
            cur.sign = val;
        } else {
            pushdown(cur);
            long mid = (cur.rgLeft + cur.rgRight) >> 1;
            if (l <= mid) update(cur.left(), l, r, val);
            if (r >= mid + 1) update(cur.right(), l, r, val);
            pushup(cur);
        }
    }
    void pushup(Node cur) {
        cur.val = merge(cur.left().val, cur.right().val);
    }
    private int merge(int left, int right) {
        return left & right;
    }
    void pushdown(Node cur) {
       if (cur.rgLeft != cur.rgRight) {
           if (cur.sign != -1) {
               cur.left().sign = cur.left().val = cur.sign;
               cur.right().sign = cur.right().val = cur.sign;
           }
        }
        // clear sign
        cur.sign = -1;
    }
}

850. Rectangle Area II

这道题需要用扫描线结合线段树来解。
扫描线在X方向移动，每次利用线段树求得当前被覆盖的区间长度是多少。这道题的区间覆盖和那个盖被子的挺像，就是被子是没有厚度的，所以我们只要求被子盖着的面积。你要拿完被子，才算不被覆盖。有一条两条都算被覆盖。另外你盖了2条，只拿走一条，也算被覆盖。
所以我们就用扫描线扫每一个X，基于这个X 会多出来和要移除哪些被子我们更新到线段树里。然后按照现在的X 和之前的X，就出这段被子覆盖面积（是Y轴长度）* （DELTA X），就能知道这个段里增加的面积。
这道题因为用不到QUERY，因为他每次只需要查询根节点的总覆盖面积。所以更新的时候虽然是区间更新，但是其实搜不到子孩子（甚至不会被创建出来），也就没必要下推懒标记。那么就不需要PUSHDOWN了。
然后VAL 要表示的是这个区间盖了基层被子。如果这个区间盖被子的数量>1，那么就返回他的全部区间范围。否则的话，就要返回他左孩子的覆盖范围+右孩子的覆盖范围。
这个过程需要自底向上更新好。所以我们要维护1个CNT，和1个VAL。CNT代表盖了多少被子，VAL代表覆盖的范围是多少。如果cnt是0，val = left.val + right.val
如果>0，val = rgRight - rgLeft

image.png
这道题因为他的特殊性，线段树模板改的稍微多一些（相比之前都只要写2行）

1157. Online Majority Element In Subarray

这道题，其实是基于数组的区间去做QUERY的，所以非常容易想到可以用线段树。
但是题目要求返回的是满足THRESHOLD条件的众数。因为1个区间众数只可能有一个（要超过半数），所以我们需要维护区间最有可能的那个众数。但是只是最有可能要判断是不是众数，还需要再CHECK一次。
众数候选人是否满足区间可加性呢？
拿到候选人如何不用O (n)的时间去判断它是否是真的符合THRESHOLD条件呢？

这2个点还是需要思考的。
后者我们拿到一个候选值，我们可以根据这个值把它所有涉及到的下标都存好。那么就可以根据QUERY的范围去做2次2分查找，分别找到下标的左边界和右边界。然后就能知道这个区间一共有多少个候选数，来判断是否符合THRESHOLD条件。

前者是根据moore's voting 算法的特性，知道候选人是有区间可加的性质。如果2个候选人不一样，就拿票数相减，候选人是票数多的那个。如果2个候选人相同，就票数相加。
所以每个节点要维护2个数，一个是众数候选人 VAL，还有一个是他的票数。我们在这里把这2个值，都存进一个int[2]的数组里，这样可以保留很多函数接口

image.png

1353. Maximum Number of Events That Can Be Attended

这道题是每次会有一个活动，活动间可能有重叠，一个活动只要参加一天就算参加过了，问最少可以花几天参加。
这道题其实用线段树不是很好想。因为他要的不是重叠的最大高度。而是不重叠的最大高度。
那么如果按照贪心的思路，我们可以想到越早结束的，我们越放到前面去参加掉。找自己还能用的空余时间里，去匹配当前这个活动。
那么其实线段树维护区间最左可用点。我们要找到这个会议的覆盖时间里，最左边自己没参加任何活动的点。
之后选了这个点后，我们就把这个点在线段树中的可用性给抹掉。然后PUSHUP更新父亲节点的最左可用点。
我们可以把所有的用掉的点的VAL都设置为INF。
然后返回区间最小值，就是最小可用点。
查询区间时如果查到这个区间最小可用点是INF，就代表这个活动没有空余时间参加了。

class Solution {
    int inf = 100001;
    public int maxEvents(int[][] es) {
        Arrays.sort(es, (a,b)->{return a[1] - b[1];});
        int cnt = 0;
        Node root = new Node(1, es[es.length - 1][1]);
        for (int[] e : es) {
            int pos = query(root, e[0], e[1]);
            if (pos < inf) {
                cnt++;
                update(root, pos, pos, inf);
            }
        }
        return cnt;
    }
    class Node {
        long rgLeft, rgRight;
        Node left, right;
        int val;
        public Node(int start, int end) {
            rgLeft = start;
            rgRight = end;
            val = start;
        }
        public int getRangeMid() {
            return (int) (rgLeft + (rgRight - rgLeft) / 2);
        }
        public Node left() {
            if (left == null) left = new Node((int)rgLeft, getRangeMid());
            return left;
        }
        public Node right() {
            if (right == null) right = new Node(getRangeMid() + 1, (int)rgRight);
            return right;
        }
    }
    int query(Node cur, long l, long r) {
        if (l > r) return 0;
        if (cur.rgLeft >= l && cur.rgRight <= r) return cur.val;
        else {
            pushdown(cur);
            long mid = (cur.rgLeft + cur.rgRight) >> 1;
            if (r <= mid) return query(cur.left(), l, r);
            else if (l > mid) return query(cur.right(), l, r);
            return merge(query(cur.left(), l, r), query(cur.right(), l, r));
        }
    }
    void update(Node cur, int l, int r, int val) {
        if (cur.rgLeft >= l && cur.rgRight <= r) {
            cur.val = val;
        } else {
            pushdown(cur);
            long mid = (cur.rgLeft + cur.rgRight) >> 1;
            if (l <= mid) update(cur.left(), l, r, val);
            if (r >= mid + 1) update(cur.right(), l, r, val);
            pushup(cur);
        }
    }
    void pushup(Node cur) {
        cur.val = merge(cur.left().val, cur.right().val);
    }
    private int merge(int left, int right) {
        return Math.min(left, right);
    }
    void pushdown(Node cur) {
        
    }
}

673. Number of Longest Increasing Subsequence

这道题一般大家也不会想到线段树。最长上升子序列一般都会朝DP方向去想。
但是每来一个数，我们其实就是要找比这个数小的区间里最长的上升长度是多少，并且个数是多少。
叶子节点表示的就是最左端到目前这个数结尾的，最长上升子序列的长度是多少，以及有多少个。
如果7叶子节点是【2,2】， 8 叶子节点是【2,1】
那么因为2个最长长度一致，个数就可以相加了。在包含7结尾和8结尾的最长上升子序列长度是2，个数是3
如果2边最大长度不一致，那么就用最大长度更大的那个来表示这个包含更多区间结尾的最长上升子序列的信息。
主函数如下

int inf = Integer.MAX_VALUE;
public int findNumberOfLIS(int[] nums) {
    if (nums.length == 0) return 0;
    Node root = new Node(-inf-1, inf);
    for (int i : nums) {
        // 找比自己小的区间的信息
        int[] val = query(root, -inf-1, i-1);
        // 把最长上升的长度++
        val[0]++;
        update(root, i, i, val);
    }
    return root.val[1]; // 返回最长上升长度的个数
}

然后复制动态开点线段树模板，做如下修改。
因为VAL是2个数，所以返回VAL的地方都改成数组

class Node {
        long rgLeft, rgRight;
        private Node left, right; // 不要直接用左孩子， 右孩子， 用对应方法去拿
        int[] val;
        public Node(int start, int end) {
            rgLeft = start;
            rgRight = end;
            val = new int[]{0, 1};
        }
        public int getRangeMid() {
            return (int) (rgLeft + (rgRight - rgLeft) / 2);
        }
        // 返回左孩子，如果不存在就动态创建
        public Node left() {
            if (left == null) left = new Node((int)rgLeft, getRangeMid());
            return left;
        }
        // 返回右孩子，如果不存在就动态创建
        public Node right() {
            if (right == null) right = new Node(getRangeMid() + 1, (int)rgRight);
            return right;
        }
    }
    // 线段树初始化函数， cur 是当前节点， L代表查询的左区间，R代表查询的右区间
    int[] query(Node cur, long l, long r) {
        if (l > r) return new int[]{0,1};
        if (cur.rgLeft >= l && cur.rgRight <= r) return cur.val.clone();
        else {
            pushdown(cur);
            long mid = (cur.rgLeft + cur.rgRight) >> 1;
            if (r <= mid) return query(cur.left(), l, r);
            else if (l > mid) return query(cur.right(), l, r);
            return merge(query(cur.left(), l, r), query(cur.right(), l, r));
        }
    }
    // 根据父亲的懒标记，去更新孩子的VAL及懒标记
    void update(Node cur, int l, int r, int[] val) {
        if (cur.rgLeft >= l && cur.rgRight <= r) {
            cur.val = merge(cur.val, val); // 当前这个点结尾的最长长度 去和新的情况做MERGE
        } else {
            pushdown(cur);
            long mid = (cur.rgLeft + cur.rgRight) >> 1;
            if (l <= mid) update(cur.left(), l, r, val);
            if (r >= mid + 1) update(cur.right(), l, r, val);
            pushup(cur);
        }
    }
    void pushup(Node cur) {
        cur.val = merge(cur.left().val, cur.right().val);
    }
    private int[] merge(int[] left, int[] right) {
        if (left[0] > 0 && left[0] == right[0]) {  // 如果最长长度>0, 且一样的话
            return new int[]{left[0], left[1] + right[1]}; // 个数相加
        } else if (left[0] > right[0]) return left.clone(); // 用更长的那个
        return right.clone();
    }
    void pushdown(Node cur) {
        
    }

总结

我们来回顾一下，这篇文章可以学到的。首先你掌握了线段树的3个接口函数BUILD, QUERY, UPDATE。2个核心函数PUSHUP和PUSHDOWN。
其次掌握了对大数据范围需要做离散化或者动态开点，以及他们各自的优劣。
然后掌握了几种线段树的常见用法，如权值线段树（VAL是动态维护每个数值的个数），维护区间最值（最值可以是普通被子，刚性被子，厚度为0的被子）
随后是一些其他情况下的线段树的例子，表明什么是区间可加如何运用到线段树的PUSHUP和PUSHDOWN中。
最后照例给大家留2道思考题。

思考题1.

维护一个数据结构可以动态更新一个数组里的任意下标的数。并且还需要支持LOG N时间返回任意搜索区间里的，MAX SUM SUBARRAY。应该怎么做呢

比如一个数组是【1,2,3，-5,1,6】
我可以搜索下标2到下标4的区间里最大子数组的SUM。那么显然最大子数组是【3】自己，那么就返回3.

如果是搜索下标0到下标4的区间里最大子数组的SUM，那么最大子数组就是【1，2,3】，返回6

如果是搜索下标0到下标5的区间里最大子数组的SUM，那么最大子数组就是【1，2,3，-5,1,6】，返回8

思考题2

维护一个数据结构，里面有一个输入的数组
支持如下三种操作形式：

把数组中的一段数全部乘一个值；
把数组中的一段数全部加一个值；
询问数列中的一段数的和

单次操作时间复杂度<=LOG N

高级数据结构(1)-线段树

---------------------2020.7.5 更新--------------------------------

1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits

线段树的基本思想

307. Range Sum Query - Mutable

离散化和动态开点

动态开点线段树

我们就根据每道题的特质，来选取线段树最便捷的策略，开始A题之旅。

常见线段树CASE1-维护区间个数

493. Reverse Pairs

315. Count of Smaller Numbers After Self

327. Count of Range Sum

406. Queue Reconstruction by Height

常见线段树CASE2-维护区间最值

732. My Calendar III

699. Falling Squares

218. The Skyline Problem

其他线段树CASE

715. Range Module

850. Rectangle Area II

1157. Online Majority Element In Subarray

1353. Maximum Number of Events That Can Be Attended

673. Number of Longest Increasing Subsequence

总结

思考题1.

思考题2

猜你喜欢

热点阅读