前缀和

一维前缀和

• 假设$a_0=S_0=0$
• 遍历范围从1 ~ n

有N个的正整数放到数组A里，现在要求一个新的数组S，新数组的第i个数S[i]是原数组A第0到第i个数的和

想求原数组l到r的和，即为S[r] - S[l - 1]

#include <iostream>

using namespace std;

const int N = 100010;

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

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i];

    while(m --){
        int l, r;
        cin >> l >> r;
        int res = s[r] - s[l - 1];
        cout << res << endl;
    }

    return 0;
}

二维前缀和

$S[i, j]$ = 第$i$行$j$列格子左上部分所有元素的和
以$(x_1, y_1)$为左上角，$(x_2, y_2)$为右下角的子矩阵的和为：
$S[x_2, y_2] - S[x_1 - 1, y_2] - S[x_2, y_1 - 1] + S[x_1 - 1, y_1 - 1]$

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], s[N][N];

int main()
{
    scanf("%d%d%d", &n, &m, &q);

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            cin >> 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, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int res = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
        cout << res <<endl;
    }

}

差分

一维差分

给$[l,r]$加上$c$

前缀和数组$a[1],a[2]……a[n]$
构造数组使得$a[n]=b[1]+b[2]+……+b[n]$
则$b[1]=a[1],b[2]=a[2]-a[1],b[3]=a[3]-a[2]……$

模板：B[l] += c, B[r + 1] -= c

#include <iostream>

using namespace std;

const int N = 100010;

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

void insert(int l, int r, int c)
{
    b[l] += c;//a[l到n]都加上c
    b[r + 1] -= c;//a[r + 1到n]都减去c
}

int main()
{
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);

    for(int i = 1; i <= n; i ++) insert(i, i, a[i]);//构造差分数组

    while(m --)
    {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }

    for(int i = 1 ; i <= n; i ++) b[i] += b[i - 1];//对差分数组求前缀和，处理后的a[]

    for(int i = 1; i <= n; i ++) printf("%d ", b[i]);

    return 0;
}

二维差分

将$[x_1,y_1]$到$[x_2,y_2]$加上$c$

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], b[N][N];

void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;//有2加1
}
int main()
{
    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 ++ )
            insert(i, j, i, j, a[i][j]);//差分矩阵

    while (q -- )
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];//前缀和矩阵即原矩阵

    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ ) printf("%d ", b[i][j]);
        puts("");
    }

    return 0;
}

双指针

将两层循环$O(n^2)$优化到$O(n)$

模板：

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}

应用：最长连续不重复子序列

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N],b[N];
int n;

int main()
{
    cin >> n;
    int res = 0;

    for(int i = 0; i < n; i ++) cin >> a[i];
    for(int i = 0, j = 0; i < n ; i ++){
        b[a[i]] ++;
        while(j <= i && b[a[i]] > 1) b[a[j ++]] --;
        res = max(res, i - j + 1);
    }

    cout << res;

    return 0;
}

数组元素的目标和

数组$A$前一个指针$i$，数组$B$后面一个指针$j$

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int a[N], b[N];

int main()
{
    int n, m, x;
    scanf("%d%d%d", &n, &m, &x);

    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    for(int i = 0; i < m; i ++) scanf("%d", &b[i]);

    for(int i = 0, j = m - 1; i < n; i ++){
        while(j >= 0 && a[i] + b[j] > x) j --;
        if(j >= 0 && a[i] + b[j] == x) cout << i << ' ' << j << endl;
    }

    return 0;
}

判断子序列

$a[n]$和$b[m]$具有单调性

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], b[N];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    for(int i = 0; i < m; i ++) scanf("%d", &b[i]);

    int i = 0, j = 0;
    while(j < m && i < n){
        if(a[i] == b[j]) i ++;
        j ++;
    }

    if(i == n) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

位运算

模板：

• 求n的第k位数字: n >> k & 1
• 返回n的最后一位1：lowbit(n) = n & -n

应用：二进制中1的个数

#include <iostream>

using namespace std;

int lowbit(int x)
{
    return x & -x;
}
int main()
{
    int n;
    cin >> n;
    while(n --){
        int x;
        cin >> x;
        int res = 0;
        while(x){
            x -= lowbit(x);
            res ++;
        }
        cout << res << " ";
    }
}

离散化

元素储存在vector<int> alls中，排序去重，映射到新数组中（长度较小）
二分查找找到x

模板：

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}

应用：区间和

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 300010;

typedef pair<int, int> PII;

int a[N], s[N];
int n, m;
vector<int> alls;
vector<PII> add, query;

int find(int x)
{
    int l = 0, r = alls.size() - 1;

    while(l < r)
    {
        int mid = l + r >> 1;
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }

    return r + 1;
}

int main()
{
    cin >> n >> m;


    for(int i = 0; i < n; i ++){
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});
        alls.push_back(x);
    }

    for(int i = 0; i < m; i ++){
        int l ,r;
        cin >> l >> r;
        query.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
    }

    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    for(auto item : add){
        int x = find(item.first);
        a[x] += item.second;//加c
    }

    for(int i = 1; i <= alls.size(); i ++) s[i] = s[i - 1] + a[i];//求前缀和

    for(auto item : query){
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }


    return 0;
}

区间合并

模板：

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);

    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}

按区间左端点排序
二者有交集，新区间比原来区间长，延长右端点
二者没交集，结果加一

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n;
vector<PII> segs;

void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;

    for(auto seg: segs){
        if(ed < seg.first){
            if(st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);
    }

    if(st != -2e9) res.push_back({st, ed});

    segs = res;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++){
        int l , r;
        cin >> l >> r;
        segs.push_back({l, r});
    }
    merge(segs);

    cout << segs.size() << endl;
}