快速选择 & 三向切分快排

发表于 2022-06-28 更新于 2022-10-08

概述

标题这两个算法，一个是阉割版的快排，另一个是特殊优化过的快排。既然都跟快排有关系，那本文就从最基础的快速排序开始讲起吧。本文中提到的排序都将以升序为例。

快速排序

快速排序是一位叫 C. A. R. Hoare （中文名：霍尔）的强者发明的。

1960年，霍尔在对俄语词典进行排序的过程中发明了这个算法，当时他才26岁。根据霍尔的自述：“解决词典排序时，我第一个想法是使用冒泡排序，但非常幸运的是，我第二个方法就想到了快速排序。”我们完全赞同他的自我评价：“我是幸运的，以发明一种新的排序方法开始一个人的计算机职业生涯实在是太美妙了！”——《算法设计与分析基础（第三版）》

快速排序的中心思想是分治。每一轮排序中，选取一个基准数，把小于这个基准数的都放到数组的左边，把大于这个基准数的都放到数组的右边，然后把基准数放在二者的交界处。这样，我们就相当于把这个基准数放到了它排完序后该放的地方。然而此时这个数左边和右边的区间都还处于无序的状态，所以我们递归地对左右区间进行排序，最终使整个数组有序。平均而言，快速排序的时间复杂度是 O(nlogn) ，空间复杂度是 O(logn) ，但是最差的情况下，每次选取基准数时刚好是区间内的最大/最小值（比如对一个降序数组进行升序排序），这样就需要递归 n-1 次。所以有写法为了尽量降低极端情况的影响，采用随机选择基准数的策略。而我比较习惯用Lomuto划分来写，就是选取区间左边第一个数作为基准数。

代码

void QuickSort(vector<int>& nums, int left, int right) {
    if (left >= right) return; //递归终止条件
    int i = left; int j = right;
    int key = left;
    while (i < j) {
        while (nums[j] >= nums[key] && i < j) j--;
        while (nums[i] <= nums[key] && i < j) i++;
        swap(nums[i], nums[j]);
    }
    swap(nums[key], nums[i]);
    QuickSort(nums, left, i - 1);
    QuickSort(nums, i + 1, right);
}

下面通过两个例题来介绍标题里的两个算法。

例题 1

LeetCode 215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1：

1 2	输入: [3,2,1,5,6,4] 和 k = 2 输出: 5

示例 2：

1 2	输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4

题解 1

这道题就是快速选择算法的经典应用场景了，它可以在 O(n) 的时间复杂度下找到这个数组第K大的数。我前面之所以说快速选择是阉割版的快速排序，是因为这两个算法的思路是一毛一样的，快速选择解决的问题可以说是快排的子问题。在快速排序中，每轮排序可以确定基准数在排序后数组中的位置，就相当于它的大小排序。例如在某一轮排序中，我们确定了基准数 a 是数组中第 k' 大的数，那么：

如果 k' = k ，说明当前的基准数就是数组第 k 大的数。
如果 k' < k ，说明我们要找的数比当前的基准数要小一些，所以我们递归地在基准数左边的区间里继续查找，而右边的区间就可以放着不动了。
如果 k' > k ，说明我们要找的数比当前的基准数要大一些，所以我们递归地在基准数右边的区间里继续查找，而左边的区间就可以放着不动了。

在理想情况下，我们每次可以将数组对半分，此时我们需要查找的次数最大是一个首项为 n ，项数为 log₂n ，公比为 1/2 的等比数列的和，即 2n-2 次，所以本算法的时间复杂度是 O(n) 。

代码：

class Solution {
private:
    int partition(vector<int>& nums, int l, int r, int k) {
        int i = l; int j = r;
        while (i < j) {
            while (nums[j] >= nums[l] && i < j) j--;
            while (nums[i] <= nums[l] && i < j) i++;
            swap(nums[i], nums[j]);
        }
        swap(nums[l], nums[i]);
        if (i == k) return nums[i];
        else if (i > k) return partition(nums, l, i - 1, k);
        else return partition(nums, i + 1, r, k);
    }
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        return partition(nums, 0, n - 1, n - k);
    }
};

注意： 每轮排序时，要先减小 j 的值，再增大 i 的值，这样可以保证 i 和 j 重合时对应的值一定是小于 key 的，这样就可以拿 key 和 nums[i] 直接交换。

例题 2

LeetCode 324. 摆动排序 II

给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。

你可以假设所有输入数组都可以得到满足题目要求的结果。

示例 1：

1
2
3

输入：nums = [1,5,1,1,6,4]
输出：[1,6,1,5,1,4]
解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。

示例 2:

1 2	输入：nums = [1,3,2,2,3,1] 输出：[2,3,1,3,1,2]

进阶： 使用 O(n) 时间复杂度或原地 O(1) 额外空间来实现。

题解 2

在特殊情况下，待排序数组可能是一个有很多重复元素的数组，而常规的快排依然会进行 logn 次遍历。而三向切分则是快速排序针对此场景的优化方案，每轮排序把小于基准数的放左边，大于基准数的放右边，而等于基准数的全部汇总放中间，这样未排序的部分就可以大大缩小。

回到正题，本题最简单的解法就是先排个序，然后左边较小的部分和右边较大的部分穿插起来排。但是当数组中重复元素等于数组长度的一半时，就会出现两个相同的数字挨着的情况，这种情况不满足题设的严格大于/小于。为了避免这种情况，我们可以将左子数组和右子数组逆序一下再穿插。

例如针对数组 [1,1,2,2,2,3] ，如果直接排序然后穿插的话，左子数组是 [1,1,2] ，右子数组是 [2,2,3] ，穿插后是 [1,2,1,2,2,3] ，不满足题目条件。而逆序后，左子数组就是 [2,1,1] ，右子数组就是 [3,2,2] ，穿插后是 [2,3,1,2,1,2] ，满足题目条件。这种算法的时间复杂度是 O(nlogn) 。

想要优化，就需要用到上面提到的三向切分快排了。稍加思索就能发现我们其实根本不需要保证两个子数组是有序的，只要能让可能挨着出现的数字一个在这头一个在那头就可以了。这个挨着出现的数字肯定是同时出现在左子数组和右子数组里的数字，而这种数字一定是数组的中位数。结合快速查找算法，我们可以预先查到这个数组的中位数是多少，然后再用三向切分的思想把中位数全部集中到数组中间，这时再把数组从中间切开穿插排列，就可以得到题目要求的数组了。

代码：

class Solution {
private:
    int QuickSelect(vector<int>& nums, int l, int r, int k) {
        int i = l; int j = r;
        while (i < j) {
            while (nums[j] >= nums[l] && i < j) j--;
            while (nums[i] <= nums[l] && i < j) i++;
            swap(nums[i], nums[j]);
        }
        swap(nums[l], nums[i]);
        if (i == k) return nums[i];
        else if (i > k) return QuickSelect(nums, l, i - 1, k);
        else return QuickSelect(nums, i + 1, r, k);
    }
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return;
        int key = QuickSelect(nums, 0, n - 1, n - n / 2);
        int left = 0; int right = n - 1; int mid = 0;
        while (mid < right) {
            if (nums[mid] < key) {
                swap(nums[mid], nums[left]);
                left++;
                mid++;
            }
            else if (nums[mid] > key) {
                swap(nums[mid], nums[right]);
                right--;
            }
            else mid++;
        }
        int m = n - n / 2;
        vector<int> temp1(nums.begin(), nums.begin() + m);
        vector<int> temp2(nums.begin() + m, nums.end());
        for (int i = 0; i < temp1.size(); i++) nums[i * 2] = temp1[temp1.size() - i - 1];
        for (int i = 0; i < temp2.size(); i++) nums[i * 2 + 1] = temp2[temp2.size() - i - 1];
        return;
    }
};

其中，快速选择找到的中位数是后面三向切分的基准数。由于三向切分只进行了一轮，所以时间复杂度是 O(n) ，而快速选择的时间复杂度是 O(n) ，所以整个算法的时间复杂度也是 O(n) 。

有的没的

在学Linux

开始学Linux了，没有闲置的设备就在电脑里装了虚拟机。每次从Linux回到Windows都有一种如释重负的轻松的感觉，刚开始转换操作系统真别扭。但是在Shell里敲指令还是很带感的！

放暑假了

19号就考完了，24号交了论文之后就正式开始暑假了。看大家的去向，好多人都找了实习，而我暑假除了社会调查的作业以外剩下的时间都能自己安排。这个暑假是这辈子过的最长的暑假了，接近三个月。要好好珍惜最后的闲暇了，退休前是不可能再有这么长的空闲了。在这里立一些暑期flag，也不追求全部都能完成，能认真地做完一两项都是好的，就是希望能好好利用这个暑假吧。

《鸟哥的Linux私房菜基础学习篇》
《计算机网络自顶向下方法》
学习数据库和SQL的相关知识
《STL源码剖析》
找一些实战项目练练手
LeetCode坚持刷题，每日一题的基础上再加练

暂时就想到这些。8说了，开卷！

没事听点歌（Jam - 七月上）

线段树复习 ①

发表于 2022-06-06

前情提要

线段树实在是太难了，今天又做到一题，已经完全想不起来怎么做了，所以复习了一下。以后每次做到又不会了就复习一下，把例题收录进来。不喜欢背代码模板，就把这次悟到的用文字描述一下吧。

修改函数 update()

需要六个参数，其中两个表示待查找的区间的左右边界，两个表示当前查找到的区间的左右边界（初始值为整棵线段树的左界和右界），一个表示当前节点的下标，最后一个表示需要修改的值（下面这道题中需要修改的值固定为 1 ，所以可以省去一个参数）。
如果当前区间和待查找区间不重叠，则直接返回。
如果当前区间被待查找区间完全包含，则修改本节点的值后为当前节点打下一个 lazytag ，表示这个节点后的所有节点都要加上 lazytag 的值。
如果当前区间和待查找区间只有部分重叠，则将当前区间一分为二，并递归地进行搜索，相当于搜索当前节点的左右两个子节点。递归搜索完毕后，用两个子节点的值更新当前节点的值。

别的暂时还没什么更深入的理解，下次再更新。

例题

LeetCode 732. 我的日程安排表 III

当 k 个日程安排有一些时间上的交叉时（例如 k 个日程安排都在同一时间内），就会产生 k 次预订。

给你一些日程安排 [start, end) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。

实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。

MyCalendarThree() 初始化对象。
int book(int start, int end) 返回一个整数 k，表示日历中存在的 k 次预定的最大值

示例：

输入：
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
输出：
[null, 1, 1, 2, 3, 3, 3]

解释：
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // 返回 1 ，第一个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(50, 60); // 返回 1 ，第二个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(10, 40); // 返回 2 ，第三个日程安排 [10, 40) 与第一个日程安排相交，所以最大 k 次预订是 2 次预订。
myCalendarThree.book(5, 15); // 返回 3 ，剩下的日程安排的最大 k 次预订是 3 次预订。
myCalendarThree.book(5, 10); // 返回 3
myCalendarThree.book(25, 55); // 返回 3

题解

由于本题 start 和 end 的数据范围很大，所以如果像之前那样暴力开 4 倍内存的话内存会溢出。所以本题中可以用哈希表来代替数组。

代码：

class MyCalendarThree {
private:
    unordered_map<int, int> tree;
    unordered_map<int, int> lazy;
    void update(int start, int end, int l, int r, int node) {
        if (start > r || end < l) return;//如果当前处理范围在需要计算的范围之外，则直接返回。
        else if (start <= l && r <= end) {
            //如果当前处理范围被需要计算的范围完全包括，则将整个节点打上一个lazytag，并将节点值加一。
            tree[node]++;
            lazy[node]++;
        }
        else {
            int leftnode = node * 2;
            int rightnode = node * 2 + 1;
            int mid = (l + r) / 2;
            update(start, end, l, mid, leftnode);
            update(start, end, mid + 1, r, rightnode);
            tree[node] = lazy[node] + max(tree[leftnode], tree[rightnode]);
        }
    }
public:
    MyCalendarThree() {

    }

    int book(int start, int end) {
        update(start, end - 1, 0, 1e9, 1);
        return tree[1];
    }
};

代码中，用 start 和 end 表示待处理的区间，用l 和 r 表示当前处理的区间。在刚开始阅读这段代码的时候我很奇怪为什么一开始打上 lazytag 的时候 node 的值已经加上一了，后面重新计算的时候还要再加 lazytag 的值，后来发现每个 node 储存的值是区间的最大值，而重新计算 node 值时它的 leftnode 和 rightnode 是没有把 lazytag 的值算上的，所以要重新加上一遍。

有的没的

忙着干活，没空写了，下次一定。

AStar 算法

发表于 2022-05-26 更新于 2024-03-25

概述

AStar算法是用于寻找图的最短路的算法，它是Dijkstra算法的进阶版。Dijkstra算法采用贪心的策略，每次选取能连接到的节点中离起点最近的一个，而AStar算法则不仅考虑某节点到起点的距离，还把节点到终点的距离纳入到评估标准中。当某节点到起点和到终点的距离之和最小时，我们认为该节点最有构成最短路径的潜力，因此选取该节点进行扩展。但是大多数情况下，我们很难知道某节点到终点的距离是多少，所以我们只能估算。在网格图中，我们常使用曼哈顿距离来估算这个值。

曼哈顿距离

A点和B点的曼哈顿距离就是A点沿着格子只能横着或竖着走，到B点的最短距离，它的值是两点的横坐标之差的绝对值加上两点的纵坐标之差的绝对值。例如，在上图中，1 到 6 的曼哈顿距离是 3 , 1 到 5 的曼哈顿距离是 4.

例题

LeetCode 675. 为高尔夫比赛砍树

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m * n 的矩阵表示，在这个矩阵中：

0 表示障碍，无法触碰
1 表示地面，可以行走
比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度

每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。

你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。

你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。如果你无法砍完所有的树，返回 -1 。

可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。

示例 1：

1
2
3

输入：forest = [[1,2,3],[0,0,4],[7,6,5]]
输出：6
解释：沿着上面的路径，你可以用 6 步，按从最矮到最高的顺序砍掉这些树。

示例 2：

1
2
3

输入：forest = [[1,2,3],[0,0,0],[7,6,5]]
输出：-1
解释：由于中间一行被障碍阻塞，无法访问最下面一行中的树。

示例 3：

输入：forest = [[2,3,4],[0,0,5],[8,7,6]]
输出：6
解释：可以按与示例 1 相同的路径来砍掉所有的树。
(0,0) 位置的树，可以直接砍去，不用算步数。

题解

由于砍树必须按从矮到高砍，我们可以把所有的树排个序，然后依次求相邻的树之间的最短距离，全部加起来就是总的最短距离。相邻的树之间的最短距离就可以用AStar算法查找。

代码：

class Solution {
private:
    vector<int> dist;
    int m;
    int n;
    int f(int start, int end) {
        //计算曼哈顿距离
        int x1 = start / n; int y1 = start % n;
        int x2 = end / n; int y2 = end % n;
        return abs(x1 - x2) + abs(y1 - y2);
    }
    int AStar(int start, int end, vector<vector<int>>& forest) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        q.push({ f(start,end),start });
        fill(dist.begin(), dist.end(), INT_MAX);
        dist[start] = 0;
        vector<int> dirs = { -1,0,1,0,-1 };
        while (!q.empty()) {
            //每轮从优先队列中弹出到起点和终点距离之和最短的点进行扩展。
            int state = q.top().second;
            q.pop();
            if (state == end) return dist[state];
            for (int i = 0; i < 4; i++) {
                int x = state / n + dirs[i]; int y = state % n + dirs[i + 1];
                if (0 <= x && x<m && 0 <= y && y < n && forest[x][y]>0 && dist[x * n + y]>dist[state] + 1) {
                    /* 如果当前节点已经被查找到过（即已经记录过dist值），
                     * 并且当前计算的到起点的距离比此前查到的距离更短，
                     * 就用当前的距离值代替原来的距离值，并将其放回到优先队列。
                     */
                    dist[x * n + y] = dist[state] + 1;
                    q.push({ dist[x * n + y] + f(x * n + y,end),x * n + y });
                }
            }
        }
        return -1;
    }
public:
    int cutOffTree(vector<vector<int>>& forest) {
        m = forest.size();
        n = forest[0].size();
        dist.resize(m * n);
        vector<pair<int, int>> trees;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (forest[i][j] > 1) {
                    trees.push_back({ forest[i][j],i * n + j });
                }
            }
        }
        sort(trees.begin(), trees.end());
        int start = 0;
        int res = 0;
        for (pair<int, int> tree : trees) {
            int end = tree.second;
            int subdist = AStar(start, end, forest);
            if (subdist == -1) return -1;
            else res += subdist;
            start = end;
        }
        return res;
    }
};

有的没的

在玉泉做核酸拿到了贴纸

贴贴纸真是可爱爱。

没事听点歌（赵雷 - 鼓楼）

状态压缩

发表于 2022-05-21 更新于 2024-03-25

概述

状态压缩就是通过位运算来将字符串、数组等数据压缩进一个32位的整数型变量。例如，对于一个只包含小写字母的字符串，我们可以用一个32位整数的低26位表示，其中1代表该字符串包含对应的小写字母，0表示该字符串不包括对应的小写字母，即字符串”ac”可以被压缩为整数5（0101）。通过状态压缩，我们可以节省内存、加快运算过程。

例题 1

LeetCode 318. 最大单词长度乘积

给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。

示例 1：

1
2
3

输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出：16 
解释：这两个单词为 "abcw", "xtfn"。

示例 2：

1
2
3

输入：words = ["a","ab","abc","d","cd","bcd","abcd"]
输出：4 
解释：这两个单词为 "ab", "cd"。

示例 3：

1
2
3

输入：words = ["a","aa","aaa","aaaa"]
输出：0 
解释：不存在这样的两个单词。

题解 1

我们可以通过上文提到的状态压缩方法将 words 中的所有字符串都压缩为一个int。由于题目只需返回最大的乘积，对于多个字符串压缩为同一个int的情况，我们只需要储存长度最长的一个。然后我们两两组合得到的int，如果对他们进行或运算得到的结果为0的话，就代表他们没有重复的字母。

代码：

class Solution {
public:
    int maxProduct(vector<string>& words) {
        unordered_map<int, int> map;
        vector<int> conditions;
        for (string str : words) {
            int i = 0;
            for (char c : str) {
                i |= 1 << (c - 'a');
            }
            if (map.count(i) <= 0) conditions.push_back(i);
            map[i] = max(map[i], (int)str.length());
        }
        int res = 0;
        for (int i = 0; i < conditions.size(); i++) {
            int num1 = conditions[i];
            for (int j = 1; j < conditions.size(); j++) {
                int num2 = conditions[j];
                if ((num1 & num2) == 0) {
                    res = max(res, map[num1] * map[num2]);
                }
            }
        }
        return res;
    }
};

注意： 在C++中，位运算的优先级是低于判断的。所以if ((num1 & num2) == 0) 不可以写为if (num1 & num2 == 0) 。

例题 2

LeetCode 464. 我能赢吗

在 “100 game” 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过 100 的玩家，即为胜者。

如果我们将游戏规则改为 “玩家不能重复使用整数” 呢？

例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。

给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家是否能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现最佳。

示例 1：

输入：maxChoosableInteger = 10, desiredTotal = 11
输出：false
解释：
无论第一个玩家选择哪个整数，他都会失败。
第一个玩家可以选择从 1 到 10 的整数。
如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。

示例 2：

1 2	输入：maxChoosableInteger = 10, desiredTotal = 0 输出：true

示例 3：

1 2	输入：maxChoosableInteger = 10, desiredTotal = 1 输出：true

题解 2

状态压缩往往和一些别的编程技巧配合使用，比如记忆化搜索、动态规划等。由于待搜索的状态被压缩进了一个int里，我们就可以很容易地储存和查找该状态对应的结果。本题就是一个例子，我们可以将所有可取的整数（题目规定不超过20）压缩进一个int中，然后进行记忆化搜索。如果当前状态此前已经搜索过了，则可以直接从字典中查找其搜索结果并返回，无需重复搜索。记忆化搜索是基于深度优先搜索的，如果当前状态未搜索过，就进行常规的深度优先搜索。

代码：

class Solution {
private:
    unordered_map<int, bool> map;
    bool dfs(int state, int cursum, int maxnum, int target) {
        if (map.count(state) <= 0) {
            bool res = false;
            for (int i = 0; i < maxnum; i++) {
                if (((state >> i) & 1) == 0) {  
                    //当前数字未被取到
                    if (cursum + i + 1 >= target) {
                        //取了当前数字就可以达到target
                        res = true;
                        break;
                    }
                    if (!dfs(state | (1 << i), cursum + i + 1, maxnum, target)) {
                        //取了当前数字无法达到target，则继续进行深度优先搜索。
                        //如果取了该数字下家无论如何都赢不了，则代表必胜，返回true.
                        res = true;
                        break;
                    }
                }
            }
            map[state] = res;//记录当前状态的胜负结果，以便后续直接查询。
        }
        return map[state];
    }
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        //如果全部数字加起来都不能到达desiredTotal，则两个人都不能赢，返回false.
        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false;
        return dfs(0, 0, maxChoosableInteger, desiredTotal);
    }
};

有的没的

为什么这么久没更新

最近在忙一些别的事情。具体地说，是在忙着当优秀学长（确实准备的很辛苦！就允许我臭屁一下吧），嘿嘿。一个丹青学生会的同学邀请我去给学弟学妹们 ~~（主要是学妹）~~ 分享一些Python的考试技巧，作为一位热心水友 ~~（好为人师）~~ ，我当然不会推辞了。于是花了一个多星期准备，一边准备一边焦虑怕自己舌头捋不顺或者讲的内容大家不爱听。还好顺利搞定了。临近期末了，可能又有一阵子要肝大作业没闲工夫来更新了。

校庆日

5月21日是浙江大学的校庆日，~~学校为了纪念，特地为大家放了一天假~~ 。在这美好的一天，我喝了心心念念已久的芝士椰椰。虽然再一次喝到了椰椰，但是我再也回不到那个第一次喝到椰椰的夏天了。最美好的时代永远是在过去，我一直在怀念曾经无数次想要逃离的生活。然后我在寝室里写了一整天的代码。花了数小时手搓了大数据分析的Apriori算法，虽然在4条测试数据时表现良好，但在面对9000+条的数据集时它卡死了，白忙活，最后还是老老实实地用R语言调包。

那年今日

去年520我一个人去电影院看了《情书》的重映。第一次接触《情书》是在高中语文书附带的读本上，看到了寻找藤井树的片段。然后就跟同学借来了书，晚上睡觉前在寝室点上灯读个两章，那段时间可能是我最文艺青年的一段时间了。

没事听点歌（李荣浩 - 王牌冤家）

滑动窗口

发表于 2022-05-05 更新于 2022-10-08

概述

没什么好说的，直接看题吧。

例题 1

先来道简单的热热身。

LeetCode 713. 乘积小于 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

示例 1：

输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。

示例 2:

1 2	输入：nums = [1,2,3], k = 0 输出：0

题解 1

一开始还以为子数组的定义是中间可以间断的，比如示例 1中 [10,2] 也可以算一个答案，于是第一反应是二进制枚举法，一看数据范围最大有 10⁴ 个元素，于是就放弃了。后面看了半天题解才反应过来，原来必须是连续的元素才能叫子数组，太坑了！

既然必须是连续的元素，那就可以用滑动窗口来枚举。每轮循环窗口右边界向右移动，再一边判断一边把左边界向右移动，得到乘积小于目标值的最大子数组，再进一步计算就可以得到当前右边界下满足条件的子数组数量。

代码：

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int l=0;int r=0;
        if(k==0) return 0;
        int n=nums.size();
        int sum=1;
        int res=0;
        for(r;r<n;r++){ //每轮循环将右边界往右滑动一个单位
            sum*=nums[r];
            while(l<=r && sum>=k){ //依据当前右边界滑动左边界
                sum/=nums[l];
                l++;
            }
            res+=r-l+1; //比当前子数组小的都满足条件
        }
        return res;
    }
};

例题 2

再来一道“稍微”难一点的，其实写起来也差不太多，只是题目绕了点。

LeetCode 30. 串联所有单词的子串

给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

1 2	输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] 输出：[]

示例 3：

1 2	输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] 输出：[6,9,12]

题解 2

由于题目说 words 里的单词长度都是相同的（记为len ），那么我们就可以每次滑动 len 的距离。考虑到 s 中的单词不一定是整倍整倍出现的，比如 s="aababab" ，words=["ab","ab","ab"] 如果只从 0 开始构建移动窗口的话会刚好错过全部的 ab 。所以我们应该把 [0,len] 中的全部数都做一遍开头。

另外一个小tips就是因为题目里是不考虑 words 中元素出现的顺序的，所以可以直接使用哈希表计数，方便统计。

代码：

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int len=words[0].size();
        int n=s.length();
        int limit=words.size()*len; //窗口长度。此处为定长，上面那题是变长。
        vector<int> res;
        unordered_map<string,int> need;
        for(string i : words) need[i]++;
        for(int i=0;i<len;i++){ //[0,len）每个都当一次开头，避免有单词被拦腰截断。
            int l=i; int r=i;
            int cnt=0;
            unordered_map<string,int> window;
            while(r<n){
                string rightstr=s.substr(r,len);
                if(need.count(rightstr)>0){
                    window[rightstr]++;
                    if(window[rightstr]==need[rightstr]) cnt++;
                }
                r+=len;
                if(r-l>limit){
                    string leftstr=s.substr(l,len);
                    if(need.count(leftstr)>0){
                        if(window[leftstr]==need[leftstr]) cnt--;
                        window[leftstr]--; //先判断是否相等再减。
                    }
                    l+=len;
                }
                if(r-l==limit && cnt==need.size()){
                    res.push_back(l);
                }
            }
        }
        return res;
    }
};

有的没的

折磨永存

从那天开始我就陷入了没有尽头的等待。我还清晰地记得中考那天，因为我已经可以去缙中了可以随便考考，于是慷慨地把手表借给了同学。考场没有闹钟（其实有，但是在教室后面，怕被打成作弊不敢回头看），忘了考的什么科目了，反正我早早地写完了题目，也不知道还剩多久时间，就在教室里干等，那简直是我记忆中最漫长的等待。现在的情况比那个时候更糟，因为那个时候我还知道等待一定是有尽头的，考试是会结束的，而现在我不知道要等多久，不知道等待有没有尽头，想放弃又怕万一再坚持一下下就可以了，而又没有足够的动力和勇气支撑我继续坚持。现在的我只是逃避接受现实所以一直在拖延罢了。情感生活上我从来就不是一个洒脱的人，在认识到这一点之后就愈发不敢轻易地对一个人动心了。

我的情感生活真是过得稀烂。 ——节选自1019事变

网抑云（孙燕姿 - 我怀念的）

LFU 缓存

发表于 2022-04-28 更新于 2022-10-08

概述

LFU（Least Frequently Used）缓存是另一种TLB中的数据调度策略。它的思想是当缓存中没有多余空间时，踢出缓存中使用次数最少的数据。

例题

LeetCode 460. LFU 缓存

请你为最不经常使用（LFU）缓存算法设计并实现数据结构。

实现 LFUCache 类：

LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象。
int get(int key) - 如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。
void put(int key, int value) - 如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。

为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入：
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
输出：
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

解释：
// cnt(x) = 键 x 的使用计数
// cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的）
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1);      // 返回 1
                 // cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
                 // cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2);      // 返回 -1（未找到）
lfu.get(3);      // 返回 3
                 // cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
                 // cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1);      // 返回 -1（未找到）
lfu.get(3);      // 返回 3
                 // cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4);      // 返回 4
                 // cache=[3,4], cnt(4)=2, cnt(3)=3

题解

哈希表+双向链表

与LRU缓存相同，我们使用哈希表来将键值映射为对应节点。LRU那题我蠢蠢地把 head 和 end 都标记为链表中的有效节点，这样处理起来会很麻烦。今天这题我选择使用“哨兵节点”，即在链表之外设置两个独立的、不储存任何数据的节点作为 head 和 end，并将更新操作独立成函数，方便后续调用。

class LFUCache {
private:
    int cap;
    int now;
    struct Node {
        int val;
        int key;
        int cnt;
        Node* prev;
        Node* next;
        Node(int v, int k) :val(v), key(k), cnt(1), prev(nullptr), next(nullptr) {};
    };
    unordered_map<int, Node* > map;
    Node* head;
    Node* end;
    void refresh(Node* node) {
        while(node->cnt >= node->next->cnt) {
            Node* ed = node->next->next;
            Node* pre = node->prev;
            Node* cur = node;
            Node* nxt = node->next;
            pre->next = nxt;
            nxt->next = cur;
            cur->next = ed;
            ed->prev = cur;
            cur->prev = nxt;
            nxt->prev = pre;
        }
        return;
    }
public:
    LFUCache(int capacity) {
        this->cap = capacity;
        this->now = 0;
        this->head = new Node(0, -1);
        this->end = new Node(0, -1);
        this->head->cnt = 0;
        this->end->cnt = INT_MAX;
        this->head->next = end;
        this->end->prev = head;
    }

    int get(int key) {
        if (map.count(key) > 0) {
            Node* cur = map[key];
            cur->cnt++;
            int res = cur->val;
            refresh(cur);
            return res;
        }
        return -1;
    }

    void put(int key, int value) {
        if (cap == 0) return;
        if (map.count(key) > 0) {
            Node* cur = map[key];
            cur->cnt++;
            cur->val = value;
            refresh(cur);
        }
        else {
            Node* newnode = new Node(value, key);
            if (now == cap) {
                map.erase(head->next->key);
                newnode->next = head->next->next;
                head->next = newnode;
                newnode->prev = head;
                newnode->next->prev = newnode;
                map[key] = newnode;
            }
            else {
                newnode->next = head->next;
                head->next = newnode;
                newnode->prev = head;
                newnode->next->prev = newnode;
                map[key] = newnode;
                now++;
            }
            refresh(newnode);
        }
        return;
    }
};

值得注意的一点是，由于同样调用次数的节点，我们要踢出最早调用过的（即 cnt 相同的若干个节点内部采用LRU算法），所以我们在更新的时候要将操作过的节点放到 cnt+1 的若干个节点中最靠后的位置，而找到这个位置当然是使用遍历的方法。所以喜闻乐见地超时了（最差的情况下时间复杂度到达平方级别）。

哈希表+二维双向链表

为了解决超时问题，我们可以借助桶排序的思想，把链表扩充为二维链表。其中一个链表使用链表储存某 cnt 值的所有节点，并按最早调用时间排序，即链表套链表。在更新时，我们只需取出调用过的节点，将这个节点取出放到包括了所有 cnt+1 的节点的那个链表的最后一位就可以了。

class LFUCache {
private:
    int cap;
    int now;
    struct Node {
        int val;
        int key;
        int cnt;
        Node* prev;
        Node* next;
        Node(int v, int k) :val(v), key(k), cnt(1), prev(nullptr), next(nullptr) {};
    };
    struct Bucket {
        int cnt;
        Node* head;
        Node* end;
        Bucket(int c) {
            head = new Node(0, -1);
            end = new Node(0, -1);
            head->cnt = 0;
            end->cnt = INT_MAX;
            head->next = end;
            end->prev = head;
            cnt = c;
        };
    };
    unordered_map<int, Node* > map;
    unordered_map<int, Bucket* > buckets;
    Bucket* buck1;
    void refresh(Node* node) {
        if (buckets.count(node->cnt) <= 0) {
            Bucket* buck = new Bucket(node->cnt);
            buckets[node->cnt] = buck;
        }
        node->next->prev = node->prev;
        node->prev->next = node->next;
        Bucket* buck = buckets[node->cnt];
        buck->end->prev->next = node;
        node->next = buck->end;
        node->prev = buck->end->prev;
        buck->end->prev = node;
    }
public:
    LFUCache(int capacity) {
        this->cap = capacity;
        this->now = 0;
        this->buck1 = new Bucket(1);
        buckets[1] = buck1;
    }

    int get(int key) {
        if (map.count(key) > 0) {
            Node* cur = map[key];
            cur->cnt++;
            int res = cur->val;
            refresh(cur);
            return res;
        }
        return -1;
    }

    void put(int key, int value) {
        if (cap == 0) return;
        if (map.count(key) > 0) {
            Node* cur = map[key];
            cur->cnt++;
            cur->val = value;
            refresh(cur);
        }
        else {
            Node* newnode = new Node(value, key);
            if (now == cap) {
                for (int i = 1; i <= buckets.size(); i++) {
                    Bucket* buck = buckets[i];
                    if (buck->head->next != buck->end) {
                        map.erase(buck->head->next->key);
                        buck->head->next->next->prev = buck->head;
                        buck->head->next = buck->head->next->next;
                        break;
                    }
                }
                now--;
            }
            newnode->prev = buck1->end->prev;
            buck1->end->prev->next = newnode;
            newnode->next = buck1->end;
            buck1->end->prev = newnode;
            map[key] = newnode;
            now++;
        }
        return;
    }
};

有的没的

为什么是冬眠舱

“冬眠”是《三体》中的设定。人可以通过“冬眠”来跨越漫长的时间。

重逢的欢喜中，他们交换了自己的经历。罗辑得知史强是两个月前苏醒的，他的白血病已经治好了，医生还发现他的肝脏病变的几率很高，可能是喝酒的原因，也顺便处理好了。其实，在他们的感觉中，两人分别到时间并不是太长，就是四五年的样子，冬眠中是没有时间感的，但在两个世纪后的新时代相遇，还是多了一层亲切感。——《三体 II · 黑暗森林》

我现在正处于一个人生的岔路口，无论是向左走还是向右走都会后悔，而且都是无法接受的后悔。所以我选择逃避，把自己的灵魂封印起来，以此度过漫长的煎熬时光，也称之为“冬眠”。我讨厌所谓的“顺其自然”，但遗憾的是我现在只能顺其自然。也许我永远没法做出选择，也许选择的权利根本不在我手上，也许未来以上帝视角回忆这段时光的我也许会觉得很可笑，但现在的我能做的也只有继续冬眠而已。

没事听点歌（李荣浩 - 不将就）

LRU 缓存

发表于 2022-04-26 更新于 2024-03-25

概述

LRU（Least Recently Used，最近最少使用）算法是地址转换旁路缓冲储存器（TLB）中数据的更新策略。TLB中存储的是虚拟地址到物理地址的映射，可以避免CPU多次在内存中查找页表来将虚拟地址转换为物理地址的时间开销。TLB的容量是有限的，所以在我们存入新的数据且TLB中没有空余容量时应当踢出一些数据。而LRU算法的思想是踢出TLB中上次使用距今最久远的数据，即最近最少使用的数据。

例题

LeetCode 146. LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

题解

因为要以 O(1) 的时间复杂度取得 key 对应的 value ，所以我们使用哈希表来储存数据。而要以 O(1) 的时间复杂度改变节点的数据，不难想到使用链表的数据结构。所以我们可以确认本题使用的数据结构是哈希表+链表，其中哈希表的键就是题目给的键，哈希表的值是我们自定义的Node类指针。

struct Node {
    int val;
    int key;
    Node* prev;
    Node* next;
    Node(int k, int v) :val(v), key(k), prev(nullptr), next(nullptr) {};
};
unordered_map<int, Node* > map;

当我们查询或修改某一个节点时，我们应该将他移到链表的末尾。这样越靠近链表末尾的节点最后一次访问的时间离现在越近。当链表中的节点数到达容量值时，我们踢出链表的头节点，并将头节点的后一个节点设置为新的头节点。

Node* curr = map[key];
if (now == 1) return curr->val;
if (curr == head) head = head->next;
if (curr == end) end = end->prev;
if (curr->prev) curr->prev->next = curr->next;
if (curr->next) curr->next->prev = curr->prev;
curr->prev = end;
curr->next = nullptr;
end->next = curr;
end = end->next

完整代码

class LRUCache {
private:
    int cap;
    int now;
    struct Node {
        int val;
        int key;
        Node* prev;
        Node* next;
        Node(int k, int v) :val(v), key(k), prev(nullptr), next(nullptr) {};
    };
    Node* head;
    Node* end;
    unordered_map<int, Node*> map;
public:
    LRUCache(int capacity) {
        this->cap = capacity;
        this->now = 0;
        head = new Node(0, 0);
        end = head;
    }

    int get(int key) {
        if (map.count(key) > 0) {
            Node* curr = map[key];
            if (now == 1) return curr->val;
            if (curr == head) head = head->next;
            if (curr == end) end = end->prev;
            if (curr->prev) curr->prev->next = curr->next;
            if (curr->next) curr->next->prev = curr->prev;
            curr->prev = end;
            curr->next = nullptr;
            end->next = curr;
            end = end->next;
            return curr->val;
        }
        return -1;
    }

    void put(int key, int value) {
        if (map.count(key) > 0) {
            Node* curr = map[key];
            if (now == 1) {
                curr->val = value;
                return;
            }
            if (curr == head) head = head->next;
            if (curr == end) end = end->prev;
            if (curr->prev) curr->prev->next = curr->next;
            if (curr->next) curr->next->prev = curr->prev;
            curr->prev = end;
            curr->next = nullptr;
            end->next = curr;
            end = end->next;
            curr->val = value;
        }
        else {
            Node* newnode = new Node(key, value);
            map[key] = newnode;
            now++;
            if (now == 1) {
                head = newnode;
                end = newnode;
                return;
            }
            end->next = newnode;
            newnode->prev = end;
            end = end->next;
            if (now > cap) {
                map.erase(head->key);
                head = head->next;
                head->prev = nullptr;
                now--;
            }
        }
        return;
    }
};

有的没的

今日最佳弔图

虽然我七选三没选物理，但是高三闲的没事的时候（正经人谁高三闲的没事啊）喜欢翻翻同桌的物理书，平时刷B站的时候也看过介绍相对论的视频，所以我能看懂这张图。太好玩儿了，哈哈！

开始学习操作系统了

上周一启动了操作系统的学习，学习资料是《操作系统导论》。今天是第九天，已经看了三百来页了，这应该是我大学以来有效阅读量最大的一段时间了吧。目前学到的知识可能还比较浅，有些地方囫囵吞枣地就过去了，以后还需要多多积累呀。这篇Blog也是在书上看到了LRU算法才想起来之前在LeetCode上好像写到过（后来发现写到过的应该是LFU，过两天也写成博客吧），才重新回去做了一遍写出来的。

没事听点歌（周杰伦 - 晴天）

线段树（下）

发表于 2022-04-19 更新于 2022-10-08

概述

上一篇文章已经介绍了线段树的基本概念和实现方式。本文将介绍线段树的进阶技巧：懒标记（Lazy Tag） 。在不使用懒标记时，每次进行区间修改其实是进行了若干次单点修改，需要消耗大量的时间。为此，我们引入了懒标记，这样我们可以仅在需要时对节点的值进行更新，否则就给整个区间打上懒标记，表示这个区间所有的值都要加上这么多，只是我还懒得去改掉。如此操作，便可以在区间修改时节省大量时间。

代码实现

准备工作

同不带懒标记的线段树一样，我们需要预留 3 ~ 4 倍于原数组的储存空间。而不同点在于，由于我们需要存储每个节点的值和它对应的懒标记，所以我们不能简单地用一个int表示，而应该使用结构体。

struct node {
    long long val = 0;
    int lazytag = 0;
};
vector<node> tree(n*4);

构建线段树（不涉及懒标记）

void buildtree(int root, int start, int end) {
    if (start == end) {
        tree[root].val = nums[start];
        return;
    }
    int leftroot = root * 2;
    int rightroot = root * 2 + 1;
    int mid = (start + end) / 2;
    buildtree(leftroot, start, mid);
    buildtree(rightroot, mid + 1, end);
    tree[root].val = tree[leftroot].val + tree[rightroot].val;
}

查询

long long query(int root, int start, int end, int l, int r) {
    if (l > end || r < start) return 0;
    int leftroot = root * 2;
    int rightroot = root * 2 + 1;
    int mid = (start + end) / 2;
    if (l <= start && r >= end) return tree[root].val;
    if (tree[root].lazytag != 0) {
        //将lazytag向下推进
        tree[leftroot].lazytag += tree[root].lazytag;
        tree[leftroot].val += (long long)(mid - start + 1) * tree[root].lazytag;
        tree[rightroot].lazytag += tree[root].lazytag;
        tree[rightroot].val += (long long)(end-mid) * tree[root].lazytag;
        tree[root].lazytag = 0;
    }
    long long res = query(leftroot, start, mid, l, r) + query(rightroot, mid + 1, end, l, r);
    tree[root].val = tree[leftroot].val + tree[rightroot].val;
    return res;
}

修改

void update(int root, int start, int end, int l, int r, int k) {
    if (l > end || r < start) return;
    int leftroot = root * 2;
    int rightroot = root * 2 + 1;
    int mid = (start + end) / 2;
    if (l <= start && r >= end) {
        //如果需要修改的区间完全覆盖当前处理的区间，则整体打上lazytag留待以后处理。
        tree[root].val += (end - start + 1) * k;
        tree[root].lazytag += k;
        return;
    }
    if (tree[root].lazytag != 0) {
        //将lazytag向下推进。
        tree[leftroot].lazytag += tree[root].lazytag;
        tree[leftroot].val += (mid - start + 1) * tree[root].lazytag;
        tree[rightroot].lazytag += tree[root].lazytag;
        tree[rightroot].val += (end-mid) * tree[root].lazytag;
        tree[root].lazytag = 0;
    }
    update(leftroot, start, mid, l, r, k);
    update(rightroot, mid + 1, end, l, r, k);
    tree[root].val = tree[leftroot].val + tree[rightroot].val;
}

题解

题目请见《线段树（上）》的例题。

class Solution {
private:
    vector<int> nums;
    struct node {
        long long val = 0;
        int lazytag = 0;
    };
    vector<node> tree;
    void buildtree(int root, int start, int end) {
        if (start == end) {
            tree[root].val = nums[start];
            return;
        }
        int leftroot = root * 2;
        int rightroot = root * 2 + 1;
        int mid = (start + end) / 2;
        buildtree(leftroot, start, mid);
        buildtree(rightroot, mid + 1, end);
        tree[root].val = tree[leftroot].val + tree[rightroot].val;
    }
    void update(int root, int start, int end, int l, int r, int k) {
        if (l > end || r < start) return;
        int leftroot = root * 2;
        int rightroot = root * 2 + 1;
        int mid = (start + end) / 2;
        if (l <= start && r >= end) {
            //如果需要修改的区间完全覆盖当前处理的区间，则整体打上lazytag留待以后处理。
            tree[root].val += (end - start + 1) * k;
            tree[root].lazytag += k;
            return;
        }
        if (tree[root].lazytag != 0) {
            //将lazytag向下推进。
            tree[leftroot].lazytag += tree[root].lazytag;
            tree[leftroot].val += (mid - start + 1) * tree[root].lazytag;
            tree[rightroot].lazytag += tree[root].lazytag;
            tree[rightroot].val += (end-mid) * tree[root].lazytag;
            tree[root].lazytag = 0;
        }
        update(leftroot, start, mid, l, r, k);
        update(rightroot, mid + 1, end, l, r, k);
        tree[root].val = tree[leftroot].val + tree[rightroot].val;
    }
    long long query(int root, int start, int end, int l, int r) {
        if (l > end || r < start) return 0;
        int leftroot = root * 2;
        int rightroot = root * 2 + 1;
        int mid = (start + end) / 2;
        if (l <= start && r >= end) return tree[root].val;
        if (tree[root].lazytag != 0) {
            tree[leftroot].lazytag += tree[root].lazytag;
            tree[leftroot].val += (long long)(mid - start + 1) * tree[root].lazytag;
            tree[rightroot].lazytag += tree[root].lazytag;
            tree[rightroot].val += (long long)(end-mid) * tree[root].lazytag;
            tree[root].lazytag = 0;
        }
        long long res = query(leftroot, start, mid, l, r) + query(rightroot, mid + 1, end, l, r);
        tree[root].val = tree[leftroot].val + tree[rightroot].val;
        return res;
    }

public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        nums.resize(n,0);
        tree.resize(n * 4);
        buildtree(1, 0, n-1);
        for (int i = 0; i < bookings.size(); i++) {
            update(1, 1, n, bookings[i][0], bookings[i][1], bookings[i][2]);
        }
        vector<int> res;
        for (int i = 1; i <= n; i++) {
            res.push_back(query(1, 1, n, i, i));
        }
        return res;
    }
};

可以看到，代码真的非常非常长，而且效率也远不如直接用差分数组来得快。所以即便线段树可以高效地完成很多任务，我们也只在迫不得已时才写线段树。

有的没的

耶复活了

前一阵子GitHub账号被封了，导致Blog直接上不来了。发了邮件申诉，刚好赶上周末美帝不上班，今晚刚解封，火速更新。不过其实GitHub被封并不影响我更新，前一阵子是忙着打CSGO去了…昨天掉大分，进入贤者模式，刚好今天解封了就更了一手。希望GitHub以后不要抽风了。

关于国际化模块

犹豫再三还是把定性研究方法导论退掉了，屁事太多了。要是周萍能把经典文献阅读搞成国际化，她就是我的永远的女神。如果不行的话就试试看选计院的国际化模块吧。申上了，爱了爱了

没事听点歌（陈奕迅 - 红玫瑰）

线段树（上）

发表于 2022-04-12 更新于 2024-03-25

概述

线段树是树状数组的进阶版。说是进阶版，其实效率并没有提高，只是泛用性更广。线段树支持高效的单点查询、单点修改、区间查询、区间修改，但是代码比树状数组更复杂，所以只有迫不得已的时候才写线段树。

线段树就是一层一层地将原数据相加合并，最后形成一棵树的数据结构。用语言可能难以描述，但是看图就懂了：

如此组织数据，就可以将区间查询的时间复杂度降低到 O(log n) ，而单点查询、单点修改的时间复杂度也被限制在可以接受的 O(log n) ，所以在数据量很大时可以有理想的效果。

做题时发现的一个缺点：由于要存储所以数据加起来的和，所以在数据较大时可能溢出。

代码实现

准备工作

由于线段树是类似完美二叉树的形式，所以我们可以使用数组来存储整棵树。对于某个下标为 root 的节点，它的左孩子节点下标为 root*2 ，右孩子节点下边为 root*2+1 。由于我们需要在原数组的基础上多储存若干个节点的和，所以线段树需要使用数倍于原数组的空间。一般上来说，我们在初始化线段树时，预留 3 ~ 4 倍于原数组的储存空间。

1	vector<int> tree(n*4,0);

构建线段树

void buildtree(int root, int start, int end){
    if(start == end){
        tree[root] = num[start];
        return;
    }
    int leftroot = root * 2;
    int rightroot = root * 2 + 1;
    int mid = (start + end) / 2;
    //递归地创建左右子树
    buildtree(leftroot,start,mid);
    buildtree(rightroot,mid+1,end);
    //左右子树创建完毕，根据左右子树根节点的值给当前的根赋值
    tree[root] = tree[leftroot] + tree[rightroot];
}

查询

int query(int root, int start, int end, int l, int r){
    //查询[l,r]区间的和。当l==r时即为单点查询。
    if(l <= start && r >= end) return tree[root];
    int leftroot = root * 2;
    int rightroot = root * 2 + 1;
    int mid = (start + end) / 2;
    int sum = 0;
    if(l <= mid) sum += query(leftroot,start,mid,l,r);
    if(r > mid) sum += query(rightroot,mid+1,end,l,r);
    return sum;
}

修改（低配版）

void update(int root, int start, int end, int l, int r, int k){
    //将区间[l,r]内全部元素加上k。当l==r时即为单点修改。
    if(start == end){
        tree[root] += k;
        return;
    }
    int leftroot = root * 2;
    int rightroot = root * 2 + 1;
    int mid = (start + end) / 2;
    if(l <= mid) update(leftroot,start,mid,l,r,k);
    if(r > mid) update(rightroot,mid+1,end,l,r,k);
    tree[root] = tree[leftroot] + tree[rightroot];
    return;
}

例题

LeetCode 1109. 航班预订统计

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firstᵢ, lastᵢ, seatsᵢ] 意味着在从 firstᵢ 到 lastᵢ （包含 firstᵢ 和 lastᵢ ）的 每个航班 上预订了 seatsᵢ 个座位。

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

示例 1:

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25
因此，answer = [10,55,45,25,25]

示例 2：

输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号        1   2
预订记录 1 ：   10  10
预订记录 2 ：       15
总座位数：      10  25
因此，answer = [10,25]

题解

本题最合适的解法是差分数组（区间修改、单点查询）。但是也可以用线段树（虽然有些杀鸡用牛刀）。

注意：真正使用线段树的方法解出本题还需要线段树的进阶写法（Lazy Tag，懒标记），我将会在《线段树（下）》中介绍 ~~（如果你还看不到这篇文章，说明我还没写）~~。以下提供的代码只可以通过约三分之二的测试用例，剩余会超时，原因是目前使用的区间修改方法时间复杂度很高（如果没算错的话，应该是 O(nlog n) ，还没真正达到 O(log n) 的级别。

class Solution {
private:
    vector<long long> tree;
    int query(int root, int start, int end, int l, int r){
        if(l<=start && r>=end) return tree[root];
        int leftroot=root*2;
        int rightroot=root*2+1;
        int mid=(start+end)/2;
        int sum=0;
        if(l<=mid) sum+=query(leftroot,start,mid,l,r);
        if(r>mid) sum+=query(rightroot,mid+1,end,l,r);
        return sum;
    }
    void update(int root, int start, int end, int l, int r, int k){
        if(start==end){
            tree[root]+=k;
            return;
        }
        int leftroot=root*2;
        int rightroot=root*2+1;
        int mid=(start+end)/2;
        if(l<=mid) update(leftroot,start,mid,l,r,k);
        if(r>mid) update(rightroot,mid+1,end,l,r,k);
        tree[root]=tree[leftroot]+tree[rightroot];
        return;
    }
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        tree.resize(4*n,0);
        for(int i=0;i<bookings.size();i++){
            update(1,1,n,bookings[i][0],bookings[i][1],bookings[i][2]);
        }
        vector<int> res;
        for(int i=1;i<=n;i++){
            res.push_back(query(1,1,n,i,i));
        }
        return res;
    }
};

有的没的

在考试中才学到的一些东西

昨天晚上考了《诗歌与哲学》这门课的结课考试，就两道题，都跟尼采有关。老师讲了一个学期的尼采，可惜我一个字没听，考到一半才意识到原来尼采不是古希腊的人。翻了半天书，看不太懂，但是看到了一段文字：

孤独者，有两种基本的性格类型：一是强者的孤独，一是弱者的孤独。前者源于个体的精神强大与体能强大，因这种强大和勇猛而傲视他人，保持个体的生存意志和生存原则，振奋自我的创造力，完成命定的事业；后者源于个体的精神强大与体能虚弱，对世界心怀仇恨与怨愤，与现实原则保持心灵的抗争，蔑视世俗者、伪信者和成功者。前者因内心与外力强大，虽孤独而勇于出击；后者因外力虚弱，虽自尊而怯于行动。孤独者善于吟唱孤独之歌，每个人在特殊的时刻，皆会有孤独的体验，但并非每个人皆能战胜孤独，迎接沸腾的生活。—— 李咏吟《文学批评学》

依然看不太懂，但是感受到了一丝触动和共鸣。也许是因为我也自诩蔑视世俗和伪信，立志做最真实的自己。人在夜来非的时候就是这么矫情吧。