算法基础acwing

第0讲 时间复杂度

一般ACM或者笔试题的时间限制是1秒或2秒。
在这种情况下，C++代码中的操作次数控制在 10^7∼10^8 为最佳。

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

数据范围	复杂度	常见算法
n≤30	指数级别	dfs+剪枝，状态压缩dp
n≤100	O(n3)	floyd，dp，高斯消元
n≤1000	O(n∗)	块状链表、分块、莫队
n≤100000	O(nlogn)	各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
n≤1000000	O(n) 以及常数较小的 O(nlogn) 算法	单调队列、 hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 O(nlogn)的做法：sort、树状数组、heap、dijkstra、spfa
n≤10000000	O(n)	双指针扫描、kmp、AC自动机、线性筛素数
n≤10^9	O()	判断质数
n≤10^18	O(logn)	最大公约数，快速幂，数位DP
n≤	O(logk*loglogk)	k表示位数O(logk*loglogk)，k表示位数 ，高精度加减、FFT/NTT

常见运算技巧

位操作技巧
看不懂系列

位操作交换符号

交换符号将正数变成负数，负数变成正数

int reversal(int a) {   return ~a + 1; }

整数取反加1，正好变成其对应的负数(补码表示)；负数取反加一，则变为其原码，即正数

整数的绝对值是其本身，负数的绝对值正好可以对其进行取反加一求得，即我们首先判断其符号位（整数右移 31 位得到 0，负数右移 31 位得到 -1,即 0xffffffff），然后根据符号进行相应的操作

int abs(int a) {
  int i = a >> 31;
  return i == 0 ? a : (~a + 1);
}

上面的操作可以进行优化，可以将 i == 0 的条件判断语句去掉。我们都知道符号位 i 只有两种情况，即 i = 0 为正，i = -1 为负。对于任何数与 0 异或都会保持不变，与 -1 即 0xffffffff 进行异或就相当于对此数进行取反,因此可以将上面三目元算符转换为((a^i)-i)，即整数时 a 与 0 异或得到本身，再减去 0，负数时与 0xffffffff 异或将 a 进行取反，然后在加上 1，即减去 i(i =-1)

int abs(int a) {
  int i = a >> 31;
  return ((a^i) - i);
}

位操作进行高低位交换

a = (a >> 8) | (a << 8);

消去x最后一位的1

x & (x - 1)

检测整数 n 是否是 2 的幂次

异或

异或参考

X^1 ~X
X^0 ~X
X^X 0

不使用四则运算求加法

int add(int a, int b)
{
    if (b == 0) return a;
    return add(a^b, (unsigned int)(a & b) << 1);
}

向上和向下取整

a/b

向上

(a+b-1)/ b

向下

a/ b

四舍五入

(a+0.5) / 10

第1讲 数据结构

1.0 链表与邻接表

826. 单链表

插入操作

//将x插入到头节点
void add_to_head(int x)
{
    e[idx] = x;      // 存放新的节点的值
    ne[idx] = head;    // 将新的节点指向head指向的节点
    head = idx;     // 头节点指向新插入的idx节点
    idx++；            // 下一个节点
}

#include <iostream>
#include <stdio.h>
using namespace std;
const int N = 100010;
//head 头节点下标
//e[i]表示节点i的值
//ne[i]当前节点i的next指针是多少
//idx 存储当前已经用到了哪个点
int head, e[N], ne[N], idx;
void init()
{
    head = -1;
    idx = 0;
}
//将x插入到头节点
void add_to_head(int x)
{
    e[idx] = x;      // 存放新的节点的值
    ne[idx] = head;    // 将新的节点指向head指向的节点
    head = idx;     // 头节点指向新插入的idx节点
    idx++；            // 下一个节点
}
//将x插入到下标是k的节点的后面
void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;
}
//将下标是k的后的一个点删除掉
void remove(int k)
{
    ne[k] = ne[ne[k]];
}
int main()
{
    int m;
    cin >> m;
    init();
    while (m--)
    {
        int k, x;
        char OP;
        cin >> OP;
        if (OP == 'H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if (OP == 'D')
        {
            cin >> k;
            if(!k) head = ne[head];
            else remove(k-1);
        }
        else if (OP == 'I')
        {
            cin >> k >> x;
            add(k - 1, x);
        }
    }
    for (int i = head;i != -1;i = ne[i])
    {
        cout << e[i] << " ";
    }
    puts("");
    return 0;
}

1.1 Tire

用来高效的存储和查找字符串

之前对这里的理解有点问题，以为是第二层的字母一定是每个字符串的第二个，其实不是
通过下面的标号可以看到第二个字符b：2， c:10, c:10 , d:21
其实是每一个字符都位于N（N是所有字符串的总长度）层中的一层。每层26个元素，是因为字母可能是a-z中的任意一个。
所以，找的时候递归的往下寻找即可。

835. Trie字符串统计

维护一个字符串集合，支持两种操作：

1. I x 向集合中插入一个字符串 xx；
2. Q x 询问一个字符串在集合中出现了多少次。

共有 NN 个操作，输入的字符串总长度不超过 10^5，字符串仅包含小写英文字母。

通过输入字符串总长度为10^5可知道，N取100010，表明每一个字符都位于其中的一层。之所以每一层有26个，是因为字母可能是a-z中的任意一个

#include <iostream>
using namespace std;
const int N = 100010; // 所有字符串的总长度
int son[N][26];
int idx;
int cnt[N];
void insert(const string& w)
{
    int p = 0; // p = 0 既是父节点，也是根节点
    for (auto &c : w) {
        int u = c - 'a';
        if (!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}
int query(const string& w)
{
    int p = 0;
    for (auto &c : w) {
        int u = c - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}
int main() 
{
    int n;
    cin >> n;
    while (n--)
    {
        string op, w;
        cin >> op >> w;
        if (op[0] == 'I')
            insert(w);
        else
            cout << query(w) << endl;
    }
    return 0;
}

#include <iostream>
using namespace std;
const int N = 100010;
int son[N][26], cnt[N], idx; // 下标是0的点，即是根节点，又是空节点
char str[N];
void insert(char str[]) // str是要插入到字符串
{
    int p = 0;
    for(int i=0;str[i];i++) //从根节点开始，从前往后遍历
    {
        int u = str[i] - 'a';
        if(!son[p][u]) son[p][u] = ++idx; // 若果不存在，直接创建出来
        p = son[p][u];
    }
    cnt[p]++; //str已经出现的次数
}
int query(char str[])
{
    int p = 0;
    for(int i=0;str[i];i++)
    {
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        char op[2];
        cin >> op >> str;
        if(op[0] == 'I') insert(str);
        else cout << query(str) << "\n";
    }
    return 0;
}

1.2 堆

根节点是从下标1开始的；

堆的构建

如果是一个个的插入点的话，就是n*log(n)的复杂度

因此选择从2/n的地方开始建堆

错误代码片段1

for (int i=1; i<n/2; i++)
    down(i);

上面构建堆的放方式是有问题的，无法保证第一个元素是最小元素
需要从n/2到1，这样建堆能保证，h[1]是最小的元素

为何这样最小的元素一定在堆顶呢？ 在down过程中会将小的元素上移，由于最后最后一层有n/2个元素。所以，第n/2个元素是从倒数第二层中的最后一个有子树的节点。 从n/2到 n/4的过程会将较小的元素换到倒数第二层中，依次交换到第一层，最小的元素也交换到了堆顶

如下图：

建堆方法是O（n）的证明

堆的操作

上移

这里使用的是小顶堆

up操作

void up(int root) {
    int son = root / 2;
    while (son && h[son] > h[root]) {
        swap(h[son], h[root]);
        root = son;
        son = root / 2;
    }

下移

这里使用的是小顶堆

/*
    判断跟节点是否是 根/左/右中的最小值，
        如果不是，交换跟节点和最小的节点，递归处理
*/
void down(int rootIdx, int size) {
    int minIdx = rootIdx;
    int ls = rootIdx * 2, rs = rootIdx * 2 + 1;
    if (ls <= size && h[ls] < h[minIdx]) minIdx = ls; 
    if (rs <= size && h[rs] < h[minIdx] minIdx = rs;
    if (minIdx != rootIdx) {
        swap(h[rootIdx], h[minIdx]);
        down(minIdx);
    }
 }

838. 堆排序

错误代码片段2

for (int i=n; i; i--) {
    swap(h[1], h[i]); // 将最小的元素放到后面
    down(1, i); //重新构建堆，将最小的元素放大堆顶
}

这里的排序也是有问题的。
由于已经将对小的元素放到最后一个位置了，因此重新down的时候，边界应该是n-1，对应这里的i-1。

最后贴一个完整的正确代码 😄

#include <iostream>
using namespace std;
const int N = 100010;
int h[N];
void down(int u, int mysize)
{
    int ls = 2 * u, rs = 2 * u + 1;
    int m = u;
    if (ls <= mysize && h[ls] < h[m]) m = ls;
    if (rs <= mysize && h[rs] < h[m]) m = rs;
    if (m != u) {
        swap(h[m], h[u]);
        down(m, mysize);
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i=1; i<=n; i++) cin >> h[i];
    for (int i=n/2; i; i--)
        down(i, n);
    for (int i=n; i>n-m; i--)
    {
        cout << h[1] << " ";
        swap(h[1], h[i]);
        down(1, i-1);
    }
    return 0;
}

1.3 并查集

1. 将两个集合合并
2. 询问两个元素是否在一个集合当中

1. 根节点的编号就是当前集合的编号
2. 每一个节点存储一下父节点是谁，递归向上查找到每一个节点属于哪一个集合
3. 路径压缩就是在寻找到根节点后，直接将节点挂在更节点下，实现0（1） 的查找

最重要的函数find，这里每次都会进行路径压缩

int find(int x) { // 返回x 的祖宗节点 + 路径压缩
    if (p[x] != x) p[x] = find(p[x]); // 如果x不是根节点，
                                      // 就将当前的节点x的父节点p[x]制定为根节点（find最后递归得到的就是跟几点）
    return p[x];
}

p[x] 中存放的是x 的父节点是谁

并查集的初始化

开始时有多少个区间，就初始化多少个并查集。

并查集的合并

将其中一个结合根节点的父节点指定为另外一个集合的根节点

836. 合并集合

#include <iostream>
using namespace std;
const int N = 100010;
int p[N];
int n, m;
int find(int x) { // 返回x 的祖宗节点 + 路径压缩
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main() {
    cin >> n >> m;
    for (int i=1; i<=n; i++) p[i] = i; //初始化时，有n个并查集 
    while (m--) {
        char op[2];
        int a, b ;
        cin >> op >> a >> b;
        if (op[0] == 'M') // 合并
            p[find(a)] = find(b); // 将a的根节点直接挂到b的根节点下
        else {              // 判断是否在一个集合中
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
}

837. 连通块中点的数量

#include <iostream>
using namespace std;
const int N = 100010;
int p[N];
int cnt[N]; // 每个集合中点的个数
int n, m;
int find(int x) { // 返回x 的祖宗节点 + 路径压缩
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main() {
    cin >> n >> m;
    for (int i=1; i<=n; i++) {
        p[i] = i;
        cnt[i] = 1;
    } 
    while (m--) {
        char op[5];
        int a, b ;
        cin >> op;
        // cout << op << endl;
        if (op[0] == 'C') {      // 合并
            cin >> a >> b;
            if (find(a) == find(b)) continue;
            cnt[find(b)] += cnt[find(a)]; // a连通块的数量 增加了 b连通块的数量
            p[find(a)] = find(b); // 将a的根节点直接挂到b的根节点下
        }
        else if (op[1] == '1') { // 判断是否在一个集合中
            cin >> a >> b;
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        } else { //
            cin >> a;
            cout << cnt[find(a)] << endl;
        }
    }
}

连通块的数量

int cnt = 0;
for (int i=0; i<n; i++)
    if (p[i] == i)
        cnt++;

因为初始化的时候，p[i] = i; 如果p[i] != i, 表明在路径压缩的时候，将i的父节点变成了别的节点

1.4 哈希表

使用场景： 将庞大的数据结构映射到小的数据范围

离散化是特殊的哈希方式（原集合需要是有序的）

一般会取一个质数作为模数，这样可以减少哈希冲突的概率（具体的原因自行搜索）

算法题中，一般是没有删除操作的， 就算是删除，也是开一个数组进行标记，不是真正的删除

插入操作

　

拉链法

#include <iostream>
#include <string.h>
using namespace std;
const int N = 100003;
int h[N];   // 存储每一个槽
int e[N];   //e[i]表示节点i的值
int ne[N];  //ne[i]当前节点i的next指针是多少
int idx;    //idx 存储当前已经用到了哪个点
void insert(int x) {
    int k = (x % N + N) % N; // +N是为了保证不为负数
    e[idx] = x;     // 新生产一个节点idx，其值为x
    ne[idx] = h[k]; // 当前节点的下一节点为h[k]
    h[k] = idx++;   // 新的头节点
}
bool find(int x) {
    int k = (x % N + N) % N;
    for (int i=h[k]; i!=-1; i=ne[i]) // 链表的最后一个节点是-1
        if (e[i] == x) 
            return true;
    return false;
}
int main () {
    int n; 
    cin >> n;   
    memset(h, -1, sizeof h);
    while (n--) {
        char op[2];
        int x;
        cin >> op >> x;
        if (*op == 'I') insert(x);
        else {
            if (find(x)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

开放寻址法

1. 哈希得到对应的idx
2. 判断当前的坑位是否有人
   1. 有人，找到下一个空的坑位
   2. 没人，直接占用

删除，找到之后，打一个标记

数字的大小通常需要开到数据范围的2～3倍

int find(int x) {
    int k = (x % N + N) % N;
    while (h[k] != null && h[k] != x) // 坑有人，且不是自己
    {
        k++;
        if (k == N) k = 0; // 到末尾了，就从头开始
    }
    return k;
}

#include <iostream>
#include <cstring>
using namespace std;
const int N = 200003, null = 0x3f3f3f3f;
int h[N]; // 槽
int find(int x) {
    int k = (x % N + N) % N;
    while (h[k] != null && h[k] != x) {
        k++;
        if (k == N) k = 0;
    }
    return k;
}
int main() {
    int n; 
    cin >> n;
    memset(h, 0x3f, sizeof h); // 清空所有的槽
    while (n--) {
        char op[2];
        int x; 
        cin >> op >> x;
        int t = find (x);
        if (*op == 'I') h[t] = x;
        else {
            if (h[t] == null) puts("No");
            else puts("Yes");
        }
    }
    return 0;
}

1.5 KMP

写代码前，写画出这张图， 记住这里有一个错位，i和j+1

模板串 next数组的计算

next[i]： p[1,j]中最长的与前缀相等的后缀，记录的是前缀中最后的一个字符的下标

计算的过程中，一直存在两个字符串错位的情况，其实是为了方便计算：
通常是拿i和j+1比较，个人觉得是为了方便写next[j]

计算next数组的过程，就是寻找p串的规律

第一个成立的原因：反证法 如果next[i-1]有更大的前后缀，由于p[i] == p[j+1], 那么next[i]也有更大的值，出现矛盾

一次简单的模拟的过程

当p[i] 和 p[j+1]一直不相等时，需要一直递归的向前移动，直到起点为止。

for (int i=2; j=0; i<=n; i++) // next[1] = 0,不需要计算
{
    while (j && p[i] != p[j+1]) // 匹配一直不成功，一直向前退
        j = ne[j];
    if (p[i] == p[j+1] ）//匹配成功，匹配下一个字符
        j++;
    ne[i] = j; //记录
}

kmp匹配过程

for (int i=1, j=0; i<=m; i++)
{
    while (j && s[i] != p[j+1]) j = ne[j];
    if (s[i] == p[j+1]) j++;
    if (j == n)
    {
        printf("%d", i-n);
        j = ne[j];
    }
}

匹配成功后，j = ne[j]回退的原因和计算next数组是一样的。
回退进行下一轮的匹配

KMP应用

1. 循环节 n - next[n]

1. 所有和前缀相等的后缀

总结

需要理解其原理（这里说的原理不是简单的模拟样例）

831. KMP字符串

#include <iostream>
using namespace std;
const int N = 100010, M = 1000010;
char p[N], s[M];
int ne[N]; // next[i]： p[1,j]中最长的与前缀相等的后缀，记录的是前缀中最后的一个字符的下标
int main()
{
    int n, m;
    cin >> n >> p+1 >> m >> s+1;
    // cal next
    for (int i=2, j=0; i<=n; i++)
    {
        while (j && p[j+1] != p[i]) j = ne[j];
        if (p[j+1] == p[i]) j++;
        ne[i] = j;
    }
    // kmp
    for (int i=1, j=0; i<=m; i++)
    {
        while (j && p[j+1] != s[i]) j = ne[j];
        if (p[j+1] == s[i]) j++;
        if (j == n)
        {
            cout << i - j << ' ';
            j = ne[j];
        }
    }
    return 0;
}

第2讲 基础算法

模板

2.1 快速排序

练习题

快速排序

使用哨兵，将元素放到哨兵的两边。

分治 ==》 边分边治

void quick_sort(int arr[], int l, int r)
{
    // 递归终止
    if(l >= r) return;
    int i = l-1, j = r+1;
    int pivot = arr[l + r >> 1]; // 哨兵
    // 以哨兵为大小，数字交换到两侧
    while(i<j)
    {
        while(arr[++i] < pivot);
        while(arr[--j] > pivot);
        if(i < j) swap(arr[i], arr[j]);     
    }
    // 分治
    quick_sort(arr, l, j);
    quick_sort(arr, j+1, r);
}

第k个数

int quick_sort(int l, int r, int k)
{
    // k一定位于[l,r]中
    if(l == r) return arr[l];
    // 初始化 左端点为哨兵
    int x = arr[l], i = l-1, j = r + 1;
    // int x = arr[i + j >> 1]; // it's ok
    while(i < j)
    {
        while(arr[++i] < x);
        while(arr[--j] > x);
        if(i<j) swap(arr[i], arr[j]);
    }
    // 哨兵位置到左区间的长度
    int SLen = j - l + 1;
    if(k <= SLen) return quick_sort(l, j, k);
    else return quick_sort(j+1, r, k-SLen); // 迭代区间长度
}

思考： i == j ?

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

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return quickSelect(nums, 0, nums.size()-1, k);
    }
    int quickSelect(vector<int>&q, int l, int r, int k)
    {
        if (l==r) return q[l];
        int i = l-1, j = r+1;
        int pivot = q[l+r>>1];
        // 从大到小排列
        while (i < j)
        {
            while (q[++i] > pivot) ;
            while (q[--j] < pivot) ;
            if (i < j) swap(q[i], q[j]);
        }
        int len = j - l + 1;
        if (k <= len) return quickSelect(q, l, j, k);
        else return quickSelect(q, j+1, r, k-len);
    }
};

2.2 归并排序

练习题

归并排序

分治 ==》 先分，后治

注意临时变量的赋值

void merge_sort(int q[], int l, int r)
{
    // 终止条件
    if(l >= r) return;
    // divide
    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid+1, r);
    // 归并
    int idx = 0, i = l, j = mid+1, temp[r-l+1];
    while(i <= mid && j <= r)
        temp[idx++] = q[i] > q[j] ? q[j++] : q[i++];
    // 处理剩余元素
    while(i <= mid) temp[idx++] = q[i++];
    while(j <= r) temp[idx++] = q[j++];
    // 赋值原数组
    for(int i=0; i<r-l+1; i++)
        q[l+i] = temp[i];     
}

template<class Iter>
void merge_sort(Iter first, Iter last)
{
    if (last - first > 1) {
        Iter middle = first + (last - first) / 2;
        merge_sort(first, middle);
        merge_sort(middle, last);
        std::inplace_merge(first, middle, last);
    }
}

148. 排序链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head ==nullptr || head->next==nullptr) return head;
        ListNode* mid = getMid(head);
        return mergeTwo(sortList(head), sortList(mid));
    }
    ListNode* getMid(ListNode* head)
    {
        ListNode* fast = head, *slow = head;
        while (fast->next != nullptr && fast->next->next!=nullptr)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        // 从中点断开链表
        ListNode* mid = slow->next;
        slow->next = nullptr;
        return mid;
    }
    ListNode* mergeTwo(ListNode* head1, ListNode* head2)
    {
        // 头节点一定初始化,否则时裸指针
        ListNode* head, *root = new ListNode(0);
        head = root;
        while (head1!=nullptr && head2!=nullptr)
        {
            if (head1->val < head2->val)
            {
                head->next = head1;
                head1 = head1->next;
            }
            else
            {
                head->next = head2;
                head2 = head2->next;
            }
            head = head->next;
        }
        head->next = head1==nullptr ? head2 : head1;
        return root->next;
    }
};

【注】

l+r>>1 向下取整， l+r+1>>1 向上取整

逆序对的数量

注意：

• 逆序对数量的计算
• 最后剩余元素是否逆序的思考

void merge_sort(int q[], int l, int r)
{
    // 终止递归
    if(l >= r) return;
    // divide
    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid+1, r);
    // merge
    int i=l, j=mid+1, k=0, temp[r-l+1];
    while(i<=mid && j<=r)
    {
        if(q[i] <= q[j])
        {
            temp[k++] =  q[i++];
        }
        else
        {
            temp[k++] = q[j++];
            num += mid-i+1;
            // 向上归并的过程中，各子区间是有序的。
            // 当出现逆序时，左边区间的未遍历元素都构成逆序
            //num++; // 所以不对
        }
    }
    // 处理剩余元素
    while(i<=mid) temp[k++] = q[i++]; // num++; //前面已经计算
    while(j<=r) temp[k++] = q[j++];
    // 替换原数组元素
    for(int i=0; i<r-l+1; i++)
        q[l+i] = temp[i];
}

2.3 二分

二分的理解

)%3D%0A%5Cleft%5C%7B%20%20%0A%20%20%20%20%20%20%20%20%20%20%5Cbegin%7Barray%7D%7Blr%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20true%2C%20l%20%3D%20mid%2C%20%5Bmid%2C%20r%5D%26%5C%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20false%2C%20r%20%3D%20mid%2B1%2C%20%5Bl%2C%20mid%2B1%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%5Cend%7Barray%7D%20%20%0A%5Cright.%0A#card=math&code=if%28check%28mid%29%29%3D%0A%5Cleft%5C%7B%20%20%0A%20%20%20%20%20%20%20%20%20%20%5Cbegin%7Barray%7D%7B%2A%2Alr%2A%2A%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20true%2C%20l%20%3D%20mid%2C%20%5Bmid%2C%20r%5D%26%5C%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20false%2C%20r%20%3D%20mid%2B1%2C%20%5Bl%2C%20mid%2B1%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%5Cend%7Barray%7D%20%20%0A%5Cright.%0A&id=GFwjF)

二分的本质：

找到区间的一个分界点，使得包含分界点的区间满足某个性质，不包含分界点的区间不满足某个性质。

• 对于第一中情况+1的说明

  (l+r) / 2是向下取整的，

  当 r = l + 1时：

  更新 l : mid = (l + (l + 1)) / 2 = l

  当true时， l被更新为l，进入无限循环

• check

  表示是否满足某个性质

常见模板

bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

练习题

数的范围

这里正好使用上了两种二分的模板

pair<int, int> search(int q[], int num, int arrLen)
{
    int first, second;
    int l = 0, r = arrLen - 1;
    while(l < r)
    {
        int mid = l + r >> 1;
        // 二分：区间是否满足某种性质
        // 左端点： 那某那么区间的值都满足>=左端点(check)
        if(q[mid] >= num) r = mid;
        else l = mid + 1;
    }
    if(arr[l] != num) // 此时l=r
    {
        return make_pair(-1, -1);
    }
    else
    {
        first = l;
        l = 0, r = arrLen - 1;
        while(l < r)
        {
            int mid = l + r + 1 >> 1; // 循环中的变量会被释放，需要重新定义
            // 右端点： 区间满足 所有的值<=右端点
            if(q[mid] <= num) l = mid;
            else r = mid - 1;
        }
        second = l; // 此时l=r
    }
    return make_pair(first, second);
}

这里有一个需要理解的地方，为啥两个模板能分别取到左右的最后一个相同的数？

34. 在排序数组中查找元素的第一个和最后一个位置

这里就需要深刻理解二分的本质：请背诵 /doge

数的三次方根

double my_sqrt3(double num)
{
    double l = -10000, r  = 10000;
    while(r - l > 1e-8)
    {
        double mid = (l + r) / 2;
        if(mid * mid * mid >= num) r = mid;
        else  l = mid;
    }
    return l;
}

2.4 前缀和与差分

快速的求出数组中某一段的和

795. 前缀和

796. 子矩阵的和

初始化的时候参考下面的图

#include <iostream>
using namespace std;
const int N = 1010;
int m, n;
int a[N][N], s[N][N];
int main()
{
    int q;
    scanf("%d%d%d", &n, &m, &q);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d", &a[i][j]);
    //初始化前缀和数组        
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
    while(q--)
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]);
    }
    return 0;
}

查分


a是原数组
b称为a 的查分
a称为b 的前缀和

b[l] += c;
b[r+1] -= c;

假设最开始时，原数组为0，那么查分数组也为0
由于原数组每一个都有值，因此可以看成是进行了n次插入操作
（这里是一个关键的需要理解的地方）

因此不需要去想查分是如何构造的的

797. 差分

#include <iostream>
using namespace std;
const int N = 100010;
int a[N], b[N];
void insert(int l, int r, int c)
{
    b[l] += c;
    b[r+1] -= c;
}
int main() 
{
    int n, m;
    cin >> n >> m;
    for (int i=1; i<=n; i++)
        cin >> a[i];
    // 插入每个元素
    for (int i=1; i<=n; i++)
        insert(i, i, a[i]);
    while (m--)
    {
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    }
    // 累加，得到前缀和 查分数组的前缀和数组也就是原数组
    for (int i=1; i<=n; i++)
        b[i] += b[i-1];
    for (int i=1; i<=n; i++)
        cout << b[i] << " ";
    cout << endl;
    return 0;
}