算法笔记1.0 | Jiely 的博客

内容时效性提醒
"本篇博客完成日期距现在已大于一年，内容可能已过时，相关技术、政策或情况可能已发生变化，建议读者查证最新信息。"

左神课程笔记#

前置基本问题:#

1. 归并分治算法#

大范围的答案等不等于左边部分 + 右边部分 + 跨越左右两边的答案#

💡考虑跨左右有序是否能提升便捷性。

归并排序:

💡归并排序是一个稳定的排序。

分成左右，merge排序

1
#include<bits/stdc++.h>
2
using namespace std;
3
const int N = 1e5+10;
4
int a[N];
5
int help[N];
6

7
void merge(int l,int r){
8
    int i = l, j = ((l + r) >> 1) + 1, t1 = 0;
9

10
    while(i <= ((l + r)>> 1) && j <= r){
11
          help[t1++] = (a[i] <= a[j]) ? a[i++] : a[j++];}
12
    while(i <= ((l + r)>> 1) ){. help[t1++] = a[i++];  }
13
    while(j <= r){. help[t1++] = a[j++];  }
14

15
    for(i = r; i >=l; i--){. a[i] = help[--t1];  }
16
}
17
void guibin(int l, int r,int n){
18
     if(l >= r) return ;
19

20
     guibin(l, (l + r) >> 1, n);
21
     guibin(((l + r) >> 1)+1, r, n);
22
     merge(l, r);
23
}

归并分治

💡

归并分治是基于归并排序，在归并排序的基础上进行分 左右 + 左右中的过渡，主要是分析左右中的过渡过程是否跟左右部分的有序性相关。

2. 随机快速排序#

基本内容与快速排序保持一致，只是在选择pivot的时候是随机选择。

💡

pivot的随机选择是从概率上讲快速排序的时间复杂度降低到O(nlogn)

快排的重要部分是 partition函数部分

1
#include<bits/stdc++.h>
2
using namespace std;
3

4
const int N = 1e5+10;
5
int nums[N];
6

7
int a,b;
8
void swap(int i, int j){
9
    int temp;
10
    temp = nums[i];
11
    nums[i] = nums[j];
12
    nums[j] = temp;
13
}
14

15
void part(int l, int r, int x){
16
    int  i = l; // 小于区域 a 大于区域 b
17
    a = l, b = r;
18
    while(i <= b){
19
         if(nums[i] < x){
20
            swap(i++,a++);
21
         }else if(nums[i] > x){
22
            swap(i, b--);
23
         }else i++;
24
    }
25
}
26

27
void quick__sort(int l, int r){
28
    if(l >= r){
29
        return;
30
    }
31
    int pivot = nums[l];
32
    part(l, r, pivot);
33
    quick__sort(l,a-1);
34
    quick__sort(b+1,r);
35
}

可以用 partition 来寻找第k大第k小 (荷兰国旗问题)#

1
#include<bits/stdc++.h>
2
using namespace std;
3

4
const int N = 1e5+10;
5
int nums[N];
6

7
int a, b;
8

9
void swap(int i, int j){
10
    int temp = nums[i];
11
    nums[i] = nums[j];
12
    nums[j] = temp;
13
}
14

15
void partition(int l, int r, int x){
16
    int i = l;
17
    a = l, b = r;
18
    while(i <= b){
19
          if(nums[i] < x){
20
            swap(i++,a++);
21
          }else if(nums[i] > x){
22
            swap(i, b--);
23
          }else i++;
24
    }
25

26
}
27
int find(int k, int n){
28
    int ans = 0;
29
    for(int l = 0, r = n; l <= r;){
30
        partition(l, r, nums[l]);
31
        if(k < a){
32
            r = a -1;
33
        }else if(k > b){
34
            l = b + 1;
35
        }else{
36
            ans = nums[k];
37
            break;
38
        }
39
    }
40

41
    return ans;
42
}

构建前缀信息（46）#

常见构建

构建前缀信息（最早最晚）出现的位置

前缀和来求区间和

sum[i] = sum[i-1] + a[i]
{l , r} → sum[r + 1] - sum[l] 2. 求区间累加和为确定值的最长长度（子数组个数）
记录 t = sum[i] - aim 的最早出现次数（i 之前的 t 的出现个数）3. 正数和负数相等的最长数组长度
正数相当于 1 负数相当于 -1 求区间为 0 1的子数组最长长度

区间大于 0 的最长数组长度（值只有 -1, 1）

aim = sum[i] - sum[j] ≥ 0
if sum[i] > 0 → ans = i
if sum[i] ≤ 0 → sum[i] -1 最早出现的位置

移除最短的数组子数组长度 sum 能被 p 整数

与余数相关
sum1 % p = a // sum2 % p = b
if(a + b % p == 0) (sum1 + sum2) % p == 0
整体 aim = sum(总) % p → 看哪个区间的的余数 (t + aim) % p == 0
find = (t + p - aim) % p (同余原理) → 与环也有关

💡

单调队列和单调栈一样，保存着对于答案的可能性，并且从栈中弹出的时候，进行计算，不进行后续的计算，一般应用于区间问题。

核心思想 : 越往后的满足要求更好的选择更好

单调队列#

单调队列基本用法 → 用来维护一个窗口里面的最值（左闭右开）

💡 因为从左弹出的时候，这个队列无论如何是没有过期下标的（要不一开始被最值从右边顶出去了，要不越界被左边弹出去了）

1
deque<int> q;
2
    for (l = r = 0; r < n; r++)
3
    {
4
        while (!q.empty() && a[r] >= a[q.back()])
5
        {
6
            q.pop_back();
7
        }
8
        q.push_back(r);
9
        if (q.size() == limit + 1)
10
        {
11
            if (l++ == q.front())
12
            {
13
                q.pop_front();
14
            }
15
        }
16
    }

优先队列扩展#

区间和小于定值的最短长度

1
 int shortestSubarray(vector<int>& nums, int k) {
2
    int n = nums.size();
3
    vector<long long> sum(n + 1, 0);
4
    deque<int> q; // 小 -> 大
5
    for(int i = 1; i <= n; i++){
6
        sum[i] = sum[i-1] + nums[i-1];
7
    }
8
    int ans = INT_MAX;
9
    q.push_back(0);
10
    for(int i = 1; i <= n; i++){
11
        while(!q.empty() && sum[i] - sum[q.front()] >= k){
12
            //cout << ans << " " << i - q.front() << endl;
13
            ans = min(ans,i - q.front());
14
            q.pop_front();
15
        }
16
        while(!q.empty() && sum[i] <= sum[q.back()]){
17
            q.pop_back();
18
        }
19
        q.push_back(i);
20
    }
21
    return ans == INT_MAX ? -1 : ans;
22
    }

双端队列吃药任务安排#

1
    int n, s;
2
    cin >> n >>s;
3
    vector<int> a(n);
4
    vector<int> b(n);
5
    for(int i = 0; i < n; i++) cin >> a[i]; // 人的体力
6
    for(int i = 0; i < n; i++) cin >> b[i]; // 任务的需求
7
    sort(a.begin(),a.end());
8
    sort(b.begin(),b.end());
9
    int ans = 0; // 最少的药丸次数
10
    deque<int> q;
11
    /*
12
          先看每一个的力所能及 放入队列中
13
      */
14

15
    for(int i = 0, p = 0; i < n; i++){
16
        while(p < n && b[p] <= a[i]){
17
            q.push_back(b[p++]);
18
        }
19
        if(!q.empty() && a[i] >= q.front()){
20
           q.pop_front();
21
        }else {
22
            while(p < n && b[p] < a[i] + s){
23
                q.push_back(b[p++]);
24
            }
25
            if(q.empty()){
26
                cout << "can't do it" << endl;
27
                return 0;
28
            }else{
29
                ans++;
30
                q.pop_back(); // 吃药取最大
31
            }
32
        }
33
    }
34
    cout << ans << endl;
35
    return 0;

单调栈#

基本使用方法维护 左右侧 比当前元素 大或者小 的最近位置

💡

构建一个栈 → 越后出现的值有更大的影响力

找出以某个值为最值的子数组（最长或者对这个子数组进行一些计算）

同时间维护左右的最近的最值

1
    stack<int> s; // 记录下标
2
    for(int i = 0; i < n; i++){
3
        while(!s.empty() && a[s.top()] >= a[i]){
4
            // i 为右边
5
            int cur = s.top(); s.pop(); // 中间
6
            int l = s.empty() ? -1 : s.top(); // 左边
7
        }
8
        s.push(i);
9
    }
10
    while(!s.empty()){
11
        int cur = s.top(); s.pop();
12
        int l = s.empty() ? -1 : s.top();
13
        ans += (cur - l) * (n - cur) * a[cur];
14
    }

创新 :

求 子数组中的最小值的和

💡

用单调栈 → 求出左右两边小于(大于) 这个值的位置 → 在这个中间 i位置的值便是最值

1
#include<bits/stdc++.h>
2
using namespace std;
3
int main(){
4
    int n;
5
    cin >> n;
6
    vector<int> a(n);
7
    for(int i = 0; i < n; i++){
8
        cin >> a[i];
9
    }
10

11
    // 在子数组中 cur 位置为最小 i 为 右边
12
    stack<int> s; // 记录下标
13
    long long ans = 0;
14
    for(int i = 0; i < n; i++){
15
        while(!s.empty() && a[s.top()] >= a[i]){
16
            int cur = s.top(); s.pop(); // 中间
17
            int l = s.empty() ? -1 : s.top(); // 左边
18
            ans += (cur - l) * (i - cur) * a[cur];
19
        }
20
        s.push(i);
21
    }
22
    while(!s.empty()){
23
        int cur = s.top(); s.pop();
24
        int l = s.empty() ? -1 : s.top();
25
        ans += (cur - l) * (n - cur) * a[cur];
26
    }
27
    return 0;
28
}

实现最小字典序（单调栈）#

💡

利用单调栈来维护一个从小到大的 stack

1
   for(int i = 0; i < a.size(); i++){
2
        in[a[i] - 'a']++;
3
    }
4

5
    stack<pair<char,int>> s;
6
    vector<bool> vis(26,false);
7

8
    for(int i = 0; i < a.size(); i++){
9
    if(!vis[a[i] - 'a']){
10
    while(!s.empty() && s.top().first > a[i] && in[s.top().first - 'a'] >= 1){
11
            vis[s.top().first- 'a'] = false;
12
            s.pop();
13
        }
14
    vis[a[i] - 'a'] = true;
15
    s.push({a[i], i});
16
    }
17
    in[a[i] - 'a']--;
18
    }
19
    string ans = "";
20

21
    while(!s.empty()){
22
        ans = s.top().first + ans;
23
        s.pop();
24
    }

滑动窗口 + 双指针（视频）#

数据结构#

前缀树（字典树）#

💡

前缀树有点像链式前向星，是一个用静态数组来连接。

重点部分

cnt:用序号表示连接，如果这个节点没有使用过，他把这个节点用cnt来编号，然后cur会使用它来跳转，会到达一个没有去过的层次。

1
int cnt = 1; // 层次编号
2
// 插入单词
3
void insert(const string& word) {
4
    int cur = 1;
5
    pass[cur]++;
6
    for (char ch : word) {
7
        int path = ch - 'a';
8
        if (tree[cur][path] == 0) {
9
            tree[cur][path] = ++cnt;
10
        }
11
         cur = tree[cur][path];
12
        pass[cur]++;
13
    }
14
    end[cur]++;
15
}
16
// 查询前缀的数量
17
int prefixNumber(const string& prefix) {
18
    int cur = 1;
19
    for (char ch : prefix) {
20
        int path = ch - 'a';
21
        if (tree[cur][path] == 0) {
22
            return 0;
23
        }
24
        cur = tree[cur][path];
25
    }
26
    return pass[cur];
27
}
28
// 删除单词
29
void deleteWord(const string& word) {
30
    if (prefixNumber(word) > 0) {
31
        int cur = 1;
32
        for (char ch : word) {
33
            int path = ch - 'a';
34
            if (--pass[tree[cur][path]] == 0) {
35
                tree[cur][path] = 0;
36
                return;
37
            }
38
            cur = tree[cur][path];
39
        }
40
        end[cur]--;
41
    }
42
}
43
// 清空前缀树
44
void clear() {
45
    memset(tree, 0, sizeof(tree));
46
    memset(pass, 0, sizeof(pass));
47
    memset(end, 0, sizeof(end));
48
    cnt = 1;
49
}

以下是关于字典树 + 二进制运算:#

1
const int N = 1e3+10;
2
const int M = 2;
3

4
int pass[N];
5
int End[N];
6
int tree[N][M];
7
int cnt = 1;
8

9
void insert(int s){
10
     int cur = 1;
11
     for(int i = 63; i >= 0; i--){
12
         int temp = ((1 << i) & s) >>i;
13
         //cout << temp << endl;
14
        if(tree[cur][temp] == 0){
15
            tree[cur][temp] = ++cnt;
16
        }
17
        cur = tree[cur][temp];
18
     }
19
     // 我如何取到这个二进制上面的值
20
}
21

22
int exam(int t){
23
    int cur = 1;
24
    int Max = 0;
25
    for(int i = 63; i >= 0; i--){
26
        int temp = (t >> i) & 1;
27
        // 最好 temp ^ aim == 1 aim == 1 ^ temp
28
        int aim = 1 ^ temp;
29
        if(tree[cur][aim] == 0){
30
           aim ^= 1;
31
        }
32
        Max |= ((temp ^ aim) << i);
33
        cur = tree[cur][aim];
34
    }
35
    return Max;
36
}

单调栈 + 单调队列#

stack st 便是单调栈的形式，只是栈中的元素是单调的。

priority_queue q 便是单调队列（优先队列）的形式，在优先队列中的元素是单调的。

并查集（模版）#

1
const int N = 1e5 + 10;
2
int father[N];
3
// 初始化并查集
4
void build(int n) {
5
    for (int i = 0; i < n; i++) {
6
        father[i] = i;
7
    }
8
}
9
// 查找元素的根，并进行路径压缩
10
int find(int i) {
11
    if (i != father[i]) {
12
        father[i] = find(father[i]);
13
    }
14
    return father[i];
15
}
16
// 判断两个元素是否属于同一个集合
17
bool isSameSet(int x, int y) {
18
    return find(x) == find(y);
19
}
20
// 合并两个集合
21
void unite(int x, int y) {
22
    father[find(x)] = find(y);
23
}

基本建图方法#

vector 数组建图

1
vector<pair<int,int>>a[10005];

链式前向星

💡 **初始的 cnt 是没有使用过的然后将这个 cnt 对应 v节点 next 表示下一条边的编号 head[u] 节点的头部边的编号** ---

u -> new -> old 一开始的 head[u] -> old 现在将 head[u] -> new 将 new 的 next -> old

1
const int N = 1e5+10;
2

3
int cnt = 0;
4
int head[N];
5
struct{
6
    int to, next, w;
7
}edge[N];
8

9
void init(){
10
    for(int i = 0; i < N; i++){
11
        head[i] = -1;
12
        edge[i].next = -1;
13
    }
14
    cnt = 1;
15
}
16

17
void add(int u, int v, int w){
18
    edge[cnt].to = v;
19
    edge[cnt].w = w;
20
    edge[cnt].next = head[u];
21
    head[u] = cnt++;
22
}
23
// 遍历方法
24
void ex(){
25
    int u ;
26
    for(int e = head[u]; e > 0; e = edge[e].next){
27
        int v = edge[e].to;
28
     }
29
}

拓扑排序#

💡 所谓的拓扑排序，其实是图论里面的一个常见手段，常用于有前后关系的节点状态问题。

常从 入度为0 的节点开始访问**。（与 priority_queue 小根堆结合应用）**

如果无法把所有的点都删掉，说明有向图里有环

1
const int N = 1e5+10;
2
int queue[N]; // 可以用 STL 代替 （queue）
3
int indegree[N];

拓扑排序扩展知识（类似树型dp）#

倍增算法 + ST表（用于区间查询最值，gcd）(先看基础dp )#

💡

原理:每一个数字都能用二进数来表示 // 尽量逼进目标值

应用: 可重复贡献问题

前提:后面的点跳的距离会大于等于前面的点

跳跃公式:ST[ i ][ p ] = ST[ ST[ i ][ p-1 ] ][ p-1] p → 跳 2 的 p 次方

从 大 → 小 尝试

仅需初始化 ST[ i ][ 0 ] ，其余可以用跳跃公式解决 // 从列开始填

Max，Min的基本代码

1
const int N = 1e3 + 10;
2
int Log2[N];
3
int stmax[N][N];
4
int stmin[N][N];
5
int num[N];
6
void bulid(int n){
7
    Log2[0] = -1;
8
    for(int i = 1; i <= n; i++){
9
        Log2[i] = Log2[i >> 1] + 1;
10
        stmax[i][0] = num[i];
11
        stmin[i][0] = num[i];
12
    }
13

14
    for(int p = 1; p <= Log2[n]; p ++){
15
        for(int i = 1; i <= n; i++){
16
            stmax[i][p] = max(stmax[i][p-1],stmax[i + (1 << (p-1))][ p-1 ]);
17
            stmin[i][p] = min(stmin[i][p-1],stmin[i + (1 << p-1)][p-1]);
18
        }
19
    }
20
}

扩展的可重复贡献区间问题:

区间与区间或 (两个相同的数字与或不会影响结果)

树上问题#

树上倍增 + LCA#

tarjian算法

💡

批量离线查询

如果访问的 ans -> u 的对应节点v 访问过 ans = v 的代表节点

理解:

1
      因为 你到这个节点的时候，对应的节点访问过了的话，那些节点是在一个集合里面的，然后 节点遍历是 属于 DFS，所以都是 分支访问，访问完这个 分支， 节点进行汇总集合。

1
void tarjan(int u, int f){
2
    vis[u] = true;
3
    for(int e = head[u]; e != 0; e = ed[e].next){
4
        int v = ed[e].to;
5
        if(v != f){
6
            tarjan(v, u);
7
            father[v] = u;
8
        }
9
    }
10

11
    for(int e = q_head[u]; e != 0; e = que[e].next){
12
        int v = que[e].to;
13
        if(vis[v]){
14
            ans[que[e].w] = find(v);
15
        }
16
    }
17
}

ST表

💡

当 Deep 深度数组到达同一层的时候所对应的节点是否相同

相同 : LCA = Deep 小的

不相同:

再次同时间跳（only 不跳到同一节点我们才跳）

ST表实现的问题 : 加快 Deep数组的跳跃过程

1
int LCA(int u, int v){
2
    /*
3
        u在下面
4
     */
5
    if(Deep[u] < Deep[v]){
6
        int t = u;
7
        u = v;
8
        v = t;
9
    }
10
    for(int i = power; i >= 0; i--){
11
        if(Deep[ST[u][i]] >= Deep[v]){
12
            u = ST[u][i];
13
        }
14
    }
15

16
    if(u == v){
17
        return v;
18
    }
19

20
    for(int i = power; i >= 0; i--){
21
        if(ST[u][i] != ST[v][i]){
22
            u = ST[u][i];
23
            v = ST[v][i];
24
        }
25
    }
26
    return ST[v][0];
27

28
}

树的重心（有一个或者两个）#

树的重心的基本定义:

最大子树的节点数足够小
每棵子树的节点数不超过总节点数的一半
所有节点汇聚到重心的步数最少

补充性质:

一棵树最多有两个重心，两个重心一定相邻
如果树上增加或者删除一个叶节点，重心最多移动一条边
将两棵树连起来，新树的重心一定在两个原来重心的连线上
如果边权为正，所有节点走向重心的总距离和最小

求法一 : 最大子树足够小

1
int ans = 0, best = INT_MAX;
2
/*
3
  重心:
4
   以当前节点为 重心，所有子树中 最大数量的子树的 数量足够小
5
*/
6
int dfs(int u, int f){
7
    Size[u] = 1;
8
    int mx = 0;
9
    for(int v = head[u]; v != 0; v = edge[v].next){
10
        int e = edge[v].to;
11
        if(e != f){
12
            dfs(e,u);
13
            Size[u] += Size[e];
14
            mx = max(mx, Size[e]);
15
        }
16
    }
17
    mx = max(mx, n - Size[u]);
18
    if(mx < best || (mx  == best && u < ans)){
19
        ans = u;
20
        mx = best;
21
    }
22

23
}

求法二 :每棵子树的节点数不超过总节点的一半

1
int Size[N];
2
vector<int> ans;
3
void dfs(int u, int f){
4
    Size[u] = 1;
5
    int Mx = 0;
6
    for(int e = head[u]; e != 0; e =edge[e].next){
7
        int v = edge[e].to;
8
        if(v != f){
9
            dfs(v,u);
10
            Size[u] += Size[v];
11
            Mx = max(Size[v], Mx);
12
        }
13
    }
14
    Mx = max(Mx, n - Size[u]);
15
    if(Mx <= n / 2){
16
        ans.push_back(u);
17
    }
18
}

扩展: 带点权的树如何求重心

仅修改一个 → Size[u] 的初始值变成了点权重 56分以上

💡

首先:重心是与边权没有关系的，所谓的点权，可以理解为一个独立的树，树中的节点数量就是点的权重

1
int Size[N];
2
int a[N];
3
vector<int> ans;
4
int sum; // sum 是总点权和
5
void dfs(int u, int f){
6
    Size[u] = a[u];
7
    int Mx = 0;
8
    for(int e = head[u]; e != 0; e =edge[e].next){
9
        int v = edge[e].to;
10
        if(v != f){
11
            dfs(v,u);
12
            Size[u] += Size[v];
13
            Mx = max(Size[v], Mx);
14
        }
15
    }
16
    Mx = max(Mx, sum - Size[u]);
17
    if(Mx <= sum / 2){
18
        ans.push_back(u);
19
    }
20
}

树的直径#

树上的最长路径

两次 DFS（仅使用没有负边权）

💡能得到路径信息 1. 从根节点找离根节点最远的点 2. 在从这个节点找离这个节点最远的点

1
/*
2
  法一: 两次dfs
3
  优点:能得到路径信息
4
*/
5
int start, End;
6

7
int di[N]; // 记录从规定节点到 当前节点到距离
8
int la[N]; // 记录路径
9

10
void dfs(int u, int f, int w){
11
      la[u] = f;
12
      di[u] = di[f] + w;
13
      for(int e = head[u]; e != 0; e = ed[e].next){
14
        int v = ed[e].to;
15
        if(v != f){
16
            dfs(v, u, ed[e].w);
17
        }
18
      }
19
}
20
pair<int,int> find_road(int n){
21
    dfs(1, 0, 0);
22
    start = 1;
23
    for(int i = 1; i <= n; i++){
24
        if(di[i] > di[start]){
25
            start = i;
26
        }
27
    }
28
    dfs(start, 0, 0);
29
    End = 1;
30
    for(int i = 1; i <= n; i++){
31
        if(di[i] > di[End]){
32
           End = i;
33
        }
34
    }
35
    return {start, End};
36
}

树型dp

💡

只能得到直径长度

1
int Max_dia = INT_MIN;
2
void dp(int u, int f){
3
    for(int e = head[u];  e != 0; e = ed[e].next){
4
        int v = ed[e].to;
5
        if(v != f){
6
            dp(v, u);
7
            Max_dia = max(Max_dia, dist[u] + dist[v] + ed[e].w);
8
            dist[u] = max(dist[u], dist[v] + ed[e].w);
9
        }
10
    }
11
}

树上差分#

点差分

边差分

树状数组（视频）#

树状数组是处理区间查询的方法。

一般处理 可差分信息（总体是由部分构成的）| 下标一定从 1 开始
怎么得到最右边的 1 → i & -i

常见有以下四种查询类型

单点增加 + 范围查询

管理范围 (去除最右边的 1（ lowbit(i) ） + 1，自己)

💡

输入的时候 tree数组用add 方法进行添加

1
int tree[N];
2
// 单点增加  区间查询
3
int n; //数组长度
4
int lowbit(int i){
5
    // 取最右边的 1
6
    return i & -i;
7
}
8
void add(int i, int w){
9
     // 下标 + 最右边的 1 的地方 + w
10
     while(i <= n){
11
        tree[i] += w;
12
        i += lowbit(i);
13
     }
14
}
15
// 1 -- r 的范围和
16
int sum(int r){
17
    // sum = tree[x] 自己 然后不断去除最右边的 1
18
    int ans = 0;
19
    while(r > 0){
20
        ans += tree[r];
21
        r -= lowbit(r);
22
    }
23
    return ans;
24
}

范围增加 + 单点查询（改成差分数组）

💡

原数组 a[i] = sum(delat[1] + …+ delat[i])

delat[i] = a[i] - a[i - 1]

差分数组可以实现原数组的区间增减

delat[l] + w, delat[r + 1] - w.

构建 tree数组的时候, add_sum( i , w);

1
int tree[N];
2
// 单点增加  区间查询
3
int n; //数组长度
4
int lowbit(int i){
5
    // 取最右边的 1
6
    return i & -i;
7
}
8
void add(int i, int w){
9
     // 下标 + 最右边的 1 的地方 + w
10
     while(i <= n){
11
        tree[i] += w;
12
        i += lowbit(i);
13
     }
14
}
15
// 查询 r 位置的值
16
int sum(int r){
17
    // sum = tree[x] 自己 然后不断去除最右边的 1
18
    int ans = 0;
19
    while(r > 0){
20
        ans += tree[r];
21
        r -= lowbit(r);
22
    }
23
    return ans;
24
}
25
// 增加 l -> r 的值
26
void add_sum(int l, int r)
27
{
28
  add(l, w),add(r + 1, -w);
29
}

范围增加 + 范围查询

💡

sum(1 → r)

= r _ Sum( delat[1 → r] ) - sum(1 → r)[(i - 1) _ delat[i] ]\

维护两个差分数组 Di + （i - 1) * Di#

1
const int N = 1e5 + 10;
2
// Di
3
int tree1[N];
4
// (i - 1) * Di
5
int tree2[N];
6

7
int n;
8
int lowbit(int i){
9
    return i & -i;
10
}
11
void add(int i, int w){
12
    int t = i;
13
    while(t <= n){
14
        tree1[t] += w;
15
        t += lowbit(t);
16
    }
17
    t = i;
18
    int W = (i - 1) * w;
19
    while(t <= n){
20
        tree2[t] += W;
21
        t += lowbit(t);
22
    }
23
}
24
void Add(int l, int r, int w){
25
    add(l, w); add(r + 1, -w);
26
}
27
// 1 -> i 的和
28
int sum(int i){
29
    int ans = 0, t = i;
30
    while(t > 0){
31
        ans += (tree1[t] * i);
32
        ans -= tree2[t];
33
        t = t - lowbit(t);
34
    }
35
    return ans;
36
}

二维的单点增加 + 范围查询

要从 1 1开始

1
const int N = 1e3 + 10;
2
const int M = 1e3 + 10;
3
int tree[N][M];
4

5
int n, m;
6
int lowbit(int i){
7
    return i & -i;
8
}
9
void add(int x, int y, int w){
10
    for(int i = x; i += lowbit(i); i <= n){
11
       for(int j = y; j += lowbit(j); j <= m){
12
        tree[i][j] += w;
13
       }
14
    }
15
}
16
// 1 -> x 1 -> y
17
int sum(int x, int y){
18
     int ans = 0;
19
     for(int i = x; i > 0; i -= lowbit(i)){
20
        for(int j = y; j > 0; j-= lowbit(j)){
21
            ans += tree[i][j];
22
        }
23
     }
24
     return ans;
25
}

二维数组的范围增加 + 范围查询

逆序队问题#

线段树#

基本线段树

动态规划（先做题目）#

背包dp （66 - 75）#

区间dp#

将大范围划分为若干个小范围的问题

状态dp#

利用二进制的 0 1 来表示节点状态

树型dp#

将子树的信息返回给父亲

数位dp#

判断 数字的可能性

换根dp#

将根节点互换，要求值的变化

轮廓线dp#

三进制状压dp#

dp优化#

字符串#

KMP#

前缀函数

💡

NEXT 函数构建

1
 前后缀 匹配长度

1
int Next[N];
2
void get_next(string s){
3
    Next[0] = -1;
4
    Next[1] = 0;
5
    int i = 2, cn = 0;
6
    // Next[i] 表示的是 1 - i-1 的最长前后缀匹配长度
7
    while(i < s.size()){
8
        if(s[i - 1] == s[cn]){
9
            Next[i++] = ++cn;
10
        }else if(cn > 0){
11
            cn = Next[cn];
12
        }else{
13
            Next[i++] = 0;
14
        }
15
    }
16
}

💡

KMP 是依靠这个前缀函数来实现的

如果当前的字符不匹配

需要检测的字符，根据 NEXT 数组向前跳转

扩展 KMP （Z数组）前缀匹配问题#

动态图展示 🔗:https://personal.utdallas.edu/~besp/demo/John2010/z-algorithm.htm

💡

Z[i] 表示 s[0 - n-1] 和 s[i - n-1] 的最长匹配长度

线性加速过程:

1
   如果在最右的最长前缀匹配区间中，会加速前缀加速匹配过程

1
const int N = 2e6 + 10;
2
int z[N];
3
void Z(string s){
4
     z[0] = 0;
5
     int n = s.size();
6
     for(int i = 0, r = 0, l = 0; i < n;i++){
7
         if(i <= r && z[i - l] < r - i + 1){
8
            z[i] = z[i - l];
9
         }else{
10
            z[i] = max(0, r - i + 1);
11
            while(i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
12
            if(i + z[i] - 1 > r){
13
                r = i + z[i] - 1;
14
                l = i;
15
            }
16
     }
17
     }
18
}

Manacher#

💡

P[i] 数组是保留了更新的数组的回文串长度

# a # a # a # 总长度为 2 * n + 1

1 2 3 4 3 2 1

1
const int N = 3e7;
2
int p[N];
3
int Max = 0;
4
string c(string s){
5
    string s1 = "#";
6
    for(auto x : s){
7
       s1 += x;
8
       s1 += '#';
9
    }
10
    return s1;
11
}
12
void manacher(string s){
13
     int n = s.length();
14
     int c = 0, r = 0;
15
     for(int i = 0, len; i < n; i++){
16
        len = r > i ? min(p[2 * c - i], r - i) : 1; // 至少的回文半径区域
17
        while(i  + len < n && i - len >= 0 && s[i + len] == s[i - len] ){
18
            len ++;
19
        }
20
        if(i + len > r){
21
            c = i;
22
            r = i + len;
23
        }
24
        Max = max(Max, len);
25
         p[i] = len;
26
     }
27
}

AC自动机#

字符串哈希#

数学#

埃式筛#

💡

如果这个元素没有访问过，便是质数，并且 这个质数的所有倍数的值就不是质数

1
void ehrlich(int n){
2
    vector<bool> vis(n + 1, false);
3
    for(int i = 2; i * i <= n; i++){
4
        if(!vis[i]){
5
            for(int j = i * i; j <= n; j +=i){
6
                vis[j] = true;
7
            }
8
        }
9
    }
10

11
    int cnt = 0; // 质数 记数 vis 未访问过的 便是质数字
12
    for(int i = 1; i <= n; i++){
13
        if(!vis[i]){
14
            cnt ++;
15
            cout << i << " ";
16
        }
17
    }cout << endl;
18
    }

乘法逆元#

逆元含义:

x\rightarrow \frac{1}{x}

法一 :扩展欧几里得求逆元

1
typedef long long LL;
2
LL ExGCD(LL a, LL mod, LL &x, LL &y){
3
    if(mod == 0){
4
        x = 1; y = 0;
5
        return a;
6
    }
7
    LL d = ExGCD(mod, a % mod, x, y), t = x;
8
    x = y; y = t - a / mod * x;
9
    return d;
10
}
11
int ExGcdInv(int a, int mod){
12
    LL x, y;
13
    ExGCD(a, mod, x, y);
14
    return (x + mod) % mod;
15
}

法二 : 快速幂求逆元

1
LL fastpow(int a, int b, int mod){
2
    LL ret = 1;
3
    while(b){
4
        if(b & 1) ret = ret * a % mod;
5
        a = a * a % mod;
6
        b >>= 1;
7
    }
8
    return ret;
9
}
10
LL FermatInv(int a, int mod){
11
    return fastpow(a, mod - 2, mod);
12
}

法三 : 费马小递推求逆元

\text{inv}[i] = ( \text{mod} - (\text{mod} \div i) ) \times \text{inv}[\text{mod} \% i] \% \text{mod}

1
int invList[mod+ 10];
2
voidGetInv(int mod)
3
{
4
    invList[1]= 1;
5
for(int i= 2; i< mod; i++)
6
        invList[i]= 1LL* (mod- mod/ i)* invList[mod% i]% mod;
7
}

容斥原理#

奇 ➕ 偶 ➖ 两个集合:

|A \cup B| = |A| + |B| - |A \cap B|

三个集合:

|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|

n个集合:

\quad \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{k=1}^{n} (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \dots < i_k \leq n} \left| A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k} \right|

快速幂#

基本快速幂

1
typedef long long LL;
2
const int mod = 1e9 + 7;
3
LL fastpow(int a, int b){
4
    LL ant = 1;
5
    while(b){
6
        if(b & 1){
7
            ant = ant * a %mod;
8
        }
9
        a = a * a %mod;
10
        b >>= 1;
11
    }
12
    return ant % mod;
13
}

矩阵快速幂

💡

矩阵快速幂常用于 DP（固定线性递归）问题

一维 k阶（k 个式子） 时间复杂度 (logn * 2^k)

f(n) = c_1 f(n-1) + c_2 f(n-2) + … + c_k f(n-k)

k维一阶

\mathbf{X}n = A \mathbf{X}{n-1}

💡

相当于第 i 位置的 ans 需要第 i-1 位置的 ans（可能是二维的，以为着需要 i-1 位置的多个答案）

矩阵快速幂的基本伪代码#

1
vector<vector<int>> multiply(vector<vector<int>> a, vector<vector<int>> b){
2
    int n = a.size();
3
    int m = b[0].size();
4
    int k = a[0].size();
5
    vector<vector<int>> ans(n, vector<int>(m));
6
    // ans[i][j] == a的 第i行 * b的 第j列
7
    for(int i = 0; i < n; i++){
8
        for(int j = 0; j < m; j++){
9
            int temp = 0;
10
            for(int t = 0; t < k; t++){
11
                ans[i][j] +=a[i][t] * b[t][j];
12
            }
13

14
        }
15
    }
16
    return ans;
17
}
18

19
vector<vector<int>> power(vector<vector<int>> a, int t){
20
    int n = a.size();
21
    vector<vector<int>> ans(n, vector<int> (n, 0));
22
    for(int i = 0; i < n; i++) ans[i][i] = 1;
23
    while(t){
24
        if(t & 1) ans = multiply(ans, a);
25
        a = multiply(a, a);
26
        t >>= 1;
27
    }
28
    return ans;
29
}

左神课程笔记#

前置基本问题:#

1. 归并分治算法#

大范围的答案 等不等于 左边部分 + 右边部分 + 跨越左右两边的答案#

2. 随机快速排序#

构建前缀信息（46）#

单调队列#

单调栈#

滑动窗口 + 双指针（视频）#

数据结构#

前缀树（字典树）#

单调栈 + 单调队列#

并查集（模版）#

基本建图方法#

拓扑排序#

倍增算法 + ST表（用于区间查询最值，gcd）(先看 基础dp )#

树上问题#

树上倍增 + LCA#

树的重心（有一个或者两个）#

树的直径#

树上差分#

树状数组（视频）#

线段树#

动态规划（先做题目）#

背包dp （66 - 75）#

区间dp#

状态dp#

树型dp#

数位dp#

换根dp#

轮廓线dp#

三进制状压dp#

dp优化#

字符串#

KMP#

Manacher#

AC自动机#

字符串哈希#

数学#

埃式筛#

乘法逆元#

容斥原理#

快速幂#

评论

大范围的答案等不等于左边部分 + 右边部分 + 跨越左右两边的答案#

倍增算法 + ST表（用于区间查询最值，gcd）(先看基础dp )#