常用数据结构

• 常用数据结构

  • 1. 单调栈 / 单调队列

    • 1. 单调栈

    • 2. 单调队列

  • 2. 并查集

    • 1. 朴素并查集

    • 2. 维护size的并查集

    • 3. 维护到祖宗节点距离的并查集

    • 4. 拓展域并查集

    • 5. 带权并查集

  • 3. 双链表

  • 4. 树状数组

    • 1. 树状数组原理

    • 2. 树状数组 + 差分

  • 5. 线段树

    • 1. 单点修改

    • 2. 区间修改（懒标记）

    • 3. 扫描线法

  • 6. treap

  • 7. 可持久化数据结构

  • 8. Trie 树 （可删除）

  • 9. KMP

  • 10. 字符串哈希

  • 11. 前缀和与差分

    • 1. 前缀和

    • 2. 差分

  • 12. 离散化

  • 13. 高精度

    • 1. 高精度加法

    • 2. 高精度减法

常用数据结构

过于基础的就不提了，主要记一下算法题里面会用到的, 从应用场景记;

1. 单调栈 / 单调队列

1. 单调栈

单调栈: 给定一个序列，求序列中左边/右边离它最近的且比它小/大的数

以找出每个数左边离他最近的比它小的数为例

stack<int> stk;
vector<int> res;
for(int i = 0; i < nums.size(); i++)
{
    while(stk.size() && stk.top() >= nums[i]) stk.pop();
    // 此时栈顶元素 (如果有) 就是左边第一个比nums[i]小的数
    stack.push(nums[i]);
}

2. 单调队列

单调队列: 滑动窗口的最值

记住单调队列存的是下标 方便判断是否已经划出窗口

int hh = 0, tt = -1;
for(int i = 0; i < n; i++)
{
    if(hh <= tt && q[hh] < i - k + 1) hh++; // 判断对头是否划出窗口;
    while(hh <= tt && nums[q[tt]] >= nums[i]) tt--;
    // 区间最小值就是队头元素
    q[++tt] = i;
}

2. 并查集

并查集可以说代码短又好用第一名，我们记的都是带路径压缩的并查集

1. 朴素并查集

int p[N];
// 并查集别忘了初始化
for(int i = 1; i <= n; i++)
    p[i] = i;

int find(int x)
{
    if(p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}
// 合并两个集合
p[find(a)] = find(b);

2. 维护size的并查集

这里注意 只有每个集合root的size才有意义哦！

int p[N], size[N];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
for(int i = 1; i <= n; i++)
    p[i] = i, size[i] = 1;

// 合并两个集合；-> root 变为 b
size[find(b)] += size[find(a)];
p[find(a)] = find(b);

3. 维护到祖宗节点距离的并查集

int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x)
    {
        int u = find(p[x]);
        d[x] += d[p[x]];
        p[x] = u;
    }
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
    p[i] = i;
    d[i] = 0;
}

// 合并a和b所在的两个集合：
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

4. 拓展域并查集

拓展域并查集的思想： 枚举 在带拓展域的并查集中，同一个集合内，只要有一个条件成立，则集合内所有元素的条件都成立

这里还是举个题来解释一下比较好(带权并查集也会举这个题来解释)

奇偶游戏

除了并查集之外 这题还有点别的处理，sum[N]表示有从S[0...i] 1的个数（前缀和）

这样，题中区间1的个数就转换为：

• 如果S[L ~ R] 有奇数个1 -> sum[L - 1] 和 sum[R] 的奇偶性相反

• 如果S[L ~ R] 有偶数个1 -> sum[L - 1] 和 sum[R] 的奇偶性相同

这里带权并查集就把每个元素的可能性都枚举出来:

x 表示 如果x是偶数

x + n 表示 如果x是 奇数

A. x, y 是同类

• 1. x是奇数, y也是奇数 => merge(x + n, y + n);

• 1. x是偶数, y也是偶数 => merge(x, y);

B. x, y 是不同类

• 1. x是奇数, y是偶数 => merge(x + n, y);

• 1. x是偶数, y是奇数 => merge(x, y + n);

查询中 如果每种都不成立 则证明一定是矛盾的

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <unordered_map>

using namespace std;

const int N = 40020;

int n, m, cnt;
unordered_map<int, int> ha;
int p[N]; // 这里因为只有奇偶 所以可以用bool值和异或解决
bool d[N];

int find(int x)
{
    if(p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}
int main()
{
    scanf("%d", &n);
    scanf("%d", &m);
    int i = 1;
    n = 2 * m;
    for(i = 1; i < N; i++) p[i] = i;
    bool flag = false;
    for(i = 1; i <= m; i++)
    {
        int oria, orib;
        string type;
        cin >> oria >> orib >> type;
        if(!ha.count(oria - 1)) ha[oria - 1] = ++cnt;
        if(!ha.count(orib)) ha[orib] = ++cnt;
        int a = ha[oria - 1], b = ha[orib];
        if(type == "even")
        {
            if(find(a + n) == find(b))
            {
                flag = true;
                break;
            }
            p[find(a)] = find(b);
            p[find(a + n)] = find(b + n);
        }
        else
        {
            if(find(a) == find(b))
            {
                flag = true;
                break;
            }
            p[find(a + n)] = find(b);
            p[find(b + n)] = find(a);
        }
    }
    if(i < m || flag) cout << i - 1 << endl;
    else cout << m << endl;
    return 0;
}

5. 带权并查集

带权并查集的思想：偏差量

带权并查集的代码和维护到祖宗节点的并查集很像, 是通过维护与a, b 与根节点的关系（距离）来推导出a, b间的相对关系；

比如本题 如果root 和 a 奇偶性相同 root 与 b 奇偶性相反 => a与b奇偶性相反

可以用异或维护， 更常见的是用0 ~ m - 1 表示状态 用mod操作来维护状态（环形关系） 指路食物链这个题

带权并查集和普通并查集在find函数和merge操作上有区别

int find(int x)
{
    if(p[x] != x)
    {
        int u = find(p[x]);
        d[x] += d[p[x]]; // 记住不是d[u]
        p[x] = u;
    }
    return p[x];
}

merge操作要补上从pa 到 pb的路径长度

int pa = find(a), pb = find(b);
if(pa != pb)
{
    p[pa] = pb;
    d[pa] = d[b] - d[a] + S; // 这里S表示 a->b的权值
}

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <unordered_map>

using namespace std;

const int N = 10010;

int n, m, cnt;
unordered_map<int, int> ha;
int p[N]; // 这里因为只有奇偶 所以可以用bool值和异或解决
bool d[N];

int find(int x)
{
    if(p[x] != x)
    {
        int u = find(p[x]);
        d[x] = d[x] ^ d[p[x]]; // 啊.. 这里因为是bool 值所以不能直接加法
        p[x] = u;
    }
    return p[x];
}
int main()
{
    scanf("%d", &n);
    scanf("%d", &m);
    int i = 1;
    for(i = 1; i<= N; i++) p[i] = i;
    bool flag = false;
    for(i = 1; i <= m; i++)
    {
        int a, b;
        string type;
        cin >> a >> b >> type;
        if(!ha.count(a - 1)) ha[a - 1] = ++cnt;
        if(!ha.count(b)) ha[b] = ++cnt;
        int pa = find(ha[a - 1]), pb = find(ha[b]);
        bool dist = false;
        if(type == "odd") dist = true;
        if(pa != pb)
        {
            p[pa] = pb;
            d[pa] = d[ha[a - 1]] ^ d[ha[b]] ^ dist;
        }
        else
        {
            if(d[ha[a - 1]] ^ d[ha[b]] != dist)
            {
                flag = true;
                break;
            }
        }
    }
    if(i < m || flag) cout << i - 1 << endl;
    else cout << m << endl;
    return 0;
}

3. 双链表

4. 树状数组

1. 树状数组原理

树状数组(FenwickTree) 的场景: 快速求前缀和 + 单点修改（修改数组其中某一个数） 这两个操作都是o(logn)

avatar

avatar

很重要一个性质：parent(i) = i + lowbit(i)

1. 单点更新

记住 记住 这里更新的是差值：新值 - 原值

int lowbit(int i)
{
    return i & (-i);
}

void update(int i, int val)
{
    while(i <= len)
    {
        tree[i] += val;
        i += lowbit(i);
    }
}

2. 求前缀和

int query(int i)
{
    int sum = 0;
    while(i > 0)
    {
        sum += tree[i];
        i -= lowbit(i);
    }
}

2. 树状数组 + 差分

树状数组用来解决单点更新和区间求和问题；那么对于对等问题 区间更新 和单点求值 要怎么解决呢？

差分+ 树状数组， 差分的思想实际就是前缀和的逆运算:

insert(l, r, val) 可以拆解为b[l] += val, b[r + 1] -= val;

b的前缀和数组实际上就是a；

这里我们把这个思想和树状数组加到一起

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 100010;

int n, m;
long long  tree[N], nums[N];

int lowbit(int i)
{
    return i & (-i);
}

void add(int i, int val)
{
    while(i <= n)
    {
        tree[i] += val;
        i += lowbit(i);
    }
}

long long  query(int i)
{
    long long res = 0;
    while(i > 0)
    {
        res += tree[i];
        i -= lowbit(i);
    }
    return res;
}
// 这里就是差分的应用
void insert(int l, int r, int val)
{
    add(l, val);
    add(r + 1, -val);
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", nums + i);
        insert(i, i, nums[i]);
    }
    while(m--)
    {
        char op[2];
        int a, b, c;
        scanf("%s", op);
        if(op[0] == 'Q')
        {
            scanf("%d", &a);
            printf("%lld\n", query(a));
        }
        else
        {
            scanf("%d%d%d", &a, &b, &c);
            insert(a, b, c);
        }
    }
    return 0;
}

3. 树状数组 + 置换k次最小字典序

class Solution {
public:
    string minInteger(string num, int k) {
        int n = num.size();
        vector<queue<int>> pos(10);
        for (int i = 0; i < n; ++i) {
            pos[num[i] - '0'].push(i + 1);
        }
        string ans;
        BIT bit(n);
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < 10; ++j) {
                if (!pos[j].empty()) {
                    int behind = bit.query(pos[j].front() + 1, n);
                    int dist = pos[j].front() + behind - i;
                    if (dist <= k) {
                        bit.update(pos[j].front());
                        pos[j].pop();
                        ans += (j + '0');
                        k -= dist;
                        break;
                    }
                }
            }
        }
        return ans;
    }
};

5. 线段树

线段树的原理这里就不硬扯了，虽然线段树能解决的题很多，但大概的数据结构框架都长一样（写错就是SegFault...） 有以下五个操作：

• pushup

• pushdown(区间修改要用到)

• build

• modify

• query

1. 单点修改

单点修改就用无需懒标记的线段树就好（懒标记能不写就别写了 正常的还写不对呢）

线段树维护的信息除了询问的答案之外，还要考虑能否从左右两个区间推断出答案, 如果不行要额外维护信息

struct Node{
    int l, int r;
    int v; ...
}

举几个例题看一看吧~

1. 最大数

给定一个正整数数列 a1,a2,…,an，每一个数都在 0∼p−1之间。

可以对这列数进行两种操作：

添加操作：向序列后添加一个数，序列长度变成 n+1 询问操作：询问这个序列中最后 L 个数中最大的数是多少。 程序运行的最开始，整数序列为空。

写一个程序，读入操作的序列，并输出询问操作的答案。

输入格式

第一行有两个正整数 m,p，意义如题目描述；

接下来 m行，每一行表示一个操作。

如果该行的内容是 Q L，则表示这个操作是询问序列中最后 _L_个数的最大数是多少；

如果是 A t，则表示向序列后面加一个数，加入的数是 (t+a) mod p。其中，t是输入的参数，a 是在这个添加操作之前最后一个询问操作的答案（如果之前没有询问操作，则 a=0）。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 200010;

int m, p;
struct Node
{
    int l, r;
    int v;  // 区间[l, r]中的最大值
}tr[N * 4];

void pushup(int u)  // 由子节点的信息，来计算父节点的信息
{
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

void build(int u, int l, int r)
{
    tr[u] = {l, r}; // 一定记得初始化区间
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;   // 树中节点，已经被完全包含在[l, r]中了

    int mid = tr[u].l + tr[u].r >> 1;
    int v = 0;
    if (l <= mid) v = query(u << 1, l, r);
    if (r > mid) v = max(v, query(u << 1 | 1, l, r));

    return v;
}

void modify(int u, int x, int v)
{
    if (tr[u].l == x && tr[u].r == x) tr[u].v = v;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}


int main()
{
    int n = 0, last = 0;
    scanf("%d%d", &m, &p);
    build(1, 1, m);

    int x;
    char op[2];
    while (m -- )
    {
        scanf("%s%d", op, &x);
        if (*op == 'Q')
        {
            last = query(1, n - x + 1, n);
            printf("%d\n", last);
        }
        else
        {
            modify(1, n + 1, (last + x) % p);
            n ++ ;
        }
    }

    return 0;
}

2. 最大连续字段和

给定长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：

1、“1 x y”，查询区间 [x,y] 中的最大连续子段和，即 maxx≤l≤r≤y {∑ri=lA[i]}。

2、“2 x y”，把 A[x] 改成 y。

对于每个查询指令，输出一个整数表示答案。

这个题显然只维护一个最大连续子段和是没有办法从左右子区间推出来当前区间的最大连续子段和的；

（可能有连续字段和横跨两个区间的情况） 所以这里要额外维护前缀和 后缀和 区间和 来实现最大连续字段和的传递（pushup）

具体看代码吧

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 500050;

struct Node{
    int l, r;
    int sum, lmax, rmax, tmax;
}tr[4 * N];

int n, m;
int w[N];

void pushup(Node& u, Node& l, Node &r)
{
    u.sum = l.sum + r.sum;
    u.lmax = max(l.lmax, l.sum + r.lmax);
    u.rmax = max(r.rmax, r.sum + l.rmax);
    u.tmax = max(max(l.tmax, r.tmax), l.rmax + r.lmax);
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r)
{
    if(l == r) tr[u] = {l, r, w[r], w[r], w[r], w[r]};
    else{
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int x, int v)
{
    if(tr[u].l == x && tr[u].r == x)    tr[u] = {x, x, v, v, v, v};
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

Node query(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u];
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        // 左边: l <= mid
        // 右边：r > mid
        // 所以下面是反过来 没有重叠部分是不可能的
        if(r <= mid) return query(u << 1, l, r);
        else if (l > mid) return query(u << 1 | 1, l, r);
        else
        {
            // 左右两边都有重叠
            Node left  = query(u << 1, l, r);
            Node right = query(u << 1 | 1, l, r);
            Node res;
            pushup(res, left, right);
            return res;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", w + i);
    build(1, 1, n);
    int k, x, y;
    while(m--)
    {
        scanf("%d%d%d", &k, &x, &y);
        if(k == 1)
        {
            // query
            if(x > y) swap(x, y);
            Node res = query(1, x, y);
            printf("%d\n", res.tmax);
        }
        else
            modify(1, x, y);
    }
    return 0;
}

3. 区间最大公约数

给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：

1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。

2、“Q l r”，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。

对于每个询问，输出一个整数表示答案。

区间最大公约数怎么考虑呢 有这样一个公式

(a, b, c, d ...) = (a, b - a, c - b, d - c, ....

这样区间求和我们就把他和差分联系起来，实际上线段树维护的是差分数组的gcd值，但是除了后面的差分值之外 还有一个a 实际上是差分数组的前缀和 所以还要额外维护一个sum值

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 500010;

int n, m;
LL w[N];
struct Node{
    int l, r;
    LL sum, d;
}tr[4 * N];

LL gcd(LL a, LL b)
{
    return b? gcd(b, a % b): a;
}
// 线段树几大套装先写了

void pushup(Node& u, Node& left, Node& right)
{
    u.d = gcd(left.d, right.d);
    u.sum = left.sum + right.sum;
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r)
{
    if(l == r) tr[u] = {l, r, w[r] - w[r - 1], w[r] - w[r - 1]};
    else
    {
        tr[u].l = l, tr[u].r = r; // 记住build初始化区间
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int x, LL v)
{
    if(tr[u].l == x && tr[u].r == x)
    {
        tr[u].sum += v;
        tr[u].d   += v;
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

Node query(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u];
    int mid = tr[u].l + tr[u].r >> 1;
    if(r <= mid) return query(u << 1, l, r);
    else if (l > mid) return query(u << 1 | 1, l, r);
    else
    {
        auto left  = query(u << 1, l, r);
        auto right = query(u << 1 | 1, l, r);
        Node res;
        pushup(res,left, right);
        return res;
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &w[i]);
    build(1, 1, n);
    char op[2];
    int x, y;
    while(m--)
    {
        scanf("%s%d%d", op, &x, &y);
        if(*op == 'Q')
        {
            Node left = query(1, 1, x);
            Node right({0, 0, 0, 0});
            if (x + 1 <= y) right = query(1, x + 1, y);
            printf("%lld\n", abs(gcd(left.sum, right.d)));
        } else {
            LL z;
            scanf("%lld", &z);
            modify(1, x, z);
            if(y + 1 <= n) modify(1, y + 1, -z);
        }
    }
    return 0;
}

2. 区间修改（懒标记）

3. 扫描线法

6. treap

7. 可持久化数据结构

8. Trie 树 （可删除）

正常的Trie树

数组模拟链表 搞struct效率会低一些

int son[N][26], cnt[N], idx;
// 0 号点计时根节点，也是空节点
// son 存储树中每个节点的子节点
// cnt 存储以每个节点结尾的单词数量

void insert(char *str)
{
    int p = 0;
    for(int i = 0; str[i]; i++) // 字符串结尾是'\0'
    {
        int u = str[i] - 'a';
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}

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];
}

支持delete操作的Trie树其实用的挺少的 用到了就来这查吧hh

class Trie
{
public:
    struct Node 
    {
        int id;
        int cnt;
        vector<Node*> son;
        Node(){
            id = -1;
            cnt = 0;
            son = vector<Node*>(26, nullptr);
        }
    }*root;

    Trie()
    {
        root = new Node();
    }
    void insert(string word, int id)
    {
        Node* p = root;
        for(auto c : word)
        {
            int u = c - 'a';
            if(p->son[u] == nullptr) p->son[u] = new Node(), p->cnt++;
            p = p->son[u];
        }
        p->id = id;
    }
    void remove(string word)
    {
        stack<Node*> stk;
        Node* p = root;
        stk.push(p);
        for(auto c : word)
        {
            int u = c - 'a';
            if(p->son[u] == nullptr) return;
            p = p->son[u];
            stk.push(p);
        }
        if(p->id == -1) return;
        if(p->cnt > 0) 
        {
            p->id = -1;
            return;
        }
        p->id = -1;
        int i = word.size() - 1;
        while(stk.size())
        {
            p = stk.top();
            stk.pop();
            if(p->cnt == 0 && p->id == -1)
            {
                stk.top()->cnt--;
                stk.top()->son[word[i--] - 'a'] = nullptr;
                //delete p;  在leetcode会有问题
            }
            else  break;
        }
    }
    bool search(string word)
    {
        Node* p = root;
        for(auto c : word)
        {
            int u = c - 'a';
            if(p->son[u] == nullptr)
                return false;     
            p = p->son[u]; 
        }
        return p->id != -1;
    }
};

9. KMP

默写就完事了

int ne[N];

// 1. 求ne数组
for(int i = 2, j = 0; i < p.size(); i++)
{
    while(j && p[i] != p[j + 1]) j = ne[j];
    if(p[i] == p[j + 1]) j++;
    ne[i] = j;
}
// 2. 匹配
for(int i = 1, j = 0; i < s.size(); i++)
{
    while(j &&s[i != p[j + 1]]) j = ne[j];
    if(s[i] == p[j + 1]) j++;
    if(j == m)
    {
        // 匹配成功的逻辑
        ...
        // 匹配成功继续向下匹配
        j = ne[j];
    }
}

10. 字符串哈希

场景：快速判断子串是否相等

字符串哈希很好用 有一大半的字符串题都可以用字符串哈希来解决（剩下估计就是KMP 还有模拟了ha）

这里 P 的经验值有131 和 13331 两种，存储哈希值用的是unsigned long long 这样mod(2 ^ 64) 可以省略（溢出直接相当于取模了）

using ULL = unsigned long long;

int P = 131;
char str[N];
ULL h[N], p[N]; // h[N]存储字符串哈希值 p[N] 存储 p^n

ULL get(int l, int r) // 这里是闭区间哦
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

// 初始化
p[0] = 1;
for(int i = 1; i <= n; i++)
{
    p[i] = P * p[i - 1];
    h[i] = h[i - 1] * P + str[i] - 'a' + 1;
}

11. 前缀和与差分

1. 前缀和

场景：快速求区间和

1. 一维前缀和 S[i] = a[1] + a[2] + ... a[i] a[l] + ... + a[r] = S[r] - S[l - 1]

2. 二维前缀和 S[i, j] = 第i行j列格子左上部分所有元素的和 以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为： S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

2. 差分

1. 一维差分

场景：多次使区间[l, r]中的每个元素同时增加or减少k

差分实际上是前缀和的逆运算 构建数组b使得 b的前缀和数组等于a

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

int n, m;
int s[N], b[N];

void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> s[i];
    // 初始化差分数组
    for(int i = 1; i <= n; i++)
    {
        // b[i] = s[i] - s[i - 1];
        insert(i, i, s[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];
        cout << b[i] << ' ';
    }
    cout << endl;
    return 0;
}

1. 二维差分

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c： S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

12. 离散化

离散化有两种：保序离散化和非保序离散化

非保序离散化就unordered_map 这里我们用到的是保序离散化（维持离散化后的大小关系）

    vector<int> alls = nums;
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end()); // vector去除重复元素
    int find(int x)
    {
        int l = 0, r = alls.size() - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(alls[i] >= x) r = mid;
            else l = mid + 1; 
        }
        return r + 1;
    }

13. 高精度

一般处理一些字符串加减乘除的问题 还有高精度&低精度的一些算法

1. 高精度加法

记住那个进位t就好

vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

2. 高精度减法

和高精度加法是类似的 只不过有一个 借位的问题

1. 借位怎么处理

2. 取余要取到整数

3. 前导0记得弹出来

vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10); // 注意这里取余的方式
        if (t < 0) t = 1; // 这里要借位
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back(); // 前导0
    return C;
}

14. RMQ

多次查询区间最大值 -> 二进制倍增

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 200010, M = 18;

int n, m;
int w[N];
int f[N][M];

void init(){
    for(int j = 0; j < M; j++) {
        for(int i = 1; i - 1 + (1 << j) <= n; i++) {
            if(!j) f[i][j] = w[i];
            else f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
        }
    }
}

int query(int l, int r) {
    int len = r - l + 1;
    int k = log(len) / log(2);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", w + i);
    init();
    scanf("%d", &m);
    for(int i = 0; i < m; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        cout << query(a, b) << endl;
    }
    return 0;
}