提前声明：大佬太强了，小白加个注释( •̀ ω •́ )y。

3.2 常用技巧精选（一）

尺取法

双指针法是指使用两个指针去遍历数组，有多种玩法，比如：

  • 快慢指针：利用两个快慢指针按同方向遍历数组，经常用于区间搜索，也被称为滑动窗口或者尺取法（像个尺子一样去遍历数组）。
  • 首尾指针：从数组的两端往彼此移动，两个指针移动的方向相反。

反转（开关问题）

书中题解使用的是差分思想（什么是差分，请自行搜索学习），将对原数组的区间操作（[l，r]）转换为对差分数组对应区间的两端（ l 和 r+1） 进行操作，从而将O(n)时间内的区间修改操作转换为O(1)的单值修改操作。

提供一个比书中更简洁的cal函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int cal(int k, vector<int>& vtc){
    int sum{}, res{}, n = vtc.size();
    //差分数组，
    vector<int> diff(n+1, 0); //注意diff的大小为n+1，对区间[l,r]的操作改为对l,r+1操作，所以要n+1
    for(int i{}; i<n; ++i){
        sum += diff[i];//sum表示当前位置需要反转的次数
        if((vtc[i] + sum) % 2 == 1){//如果是1，代表需要反转
            if(i + k -1 >=n) return -1;//如果固定区间范围不在原数组内，返回负1
            ++sum;
            ++res;//反转操作数+1
            --diff[i+k];
        }
    }
    return res;
}

弹性碰撞

先无视碰撞和半径，视为直接穿过继续运行，最后将计算结果排序，第一个数必为第一个小球的位置（如果这是第二个小球的，那么第一个小球应在第二个小球下面，则有比这个数更小的数，但这个数已经最小了，所以这是第一个小球的位置），对于第i个球，球弹的范围为【(i-1)*2R, (i-1)*2R + h】，最后要加上(i-1)*2R。

离散化

离散化，当只关心数据的大小关系时，用排名代替原数据进行处理的一种预处理方法。离散化本质上是一种哈希，它在保持原序列大小关系的前提下把其映射成正整数。当原数据很大或含有负数、小数时，难以表示为数组下标，一些算法和数据结构（如BIT）无法运作，这时我们就可以考虑将其离散化。（算法学习笔记(19): 离散化|知乎）

练习题：leecode-1036-逃离大迷宫

3.3 活用数据结构

线段树

书中给出了用线段树来实现RMQ（Range Minimum Query)。书中的线段树为一颗满二叉树。树节点编号是从0开始的。

  • 满二叉树(完美二叉树 perfect binary tree)：叶子结点都在最后一层，除叶子结点之外，每个结点的度均为2

扩展：使用线段树来维护区间和，能够实现以下功能：

  1. 将某区间每一个数加上x
  2. 对某一区间求和

P3372 【模板】线段树 1 | 洛谷

学习资料：算法学习笔记(14): 线段树

预备知识：这里的线段树是一颗完全二叉树。

  • 完全二叉树(complete binary tree)：与等高的满二叉树对应位置结点一一对应。

对完全二叉树按从上到下，从左到右的顺序一次编号1，2，…，N。（注意是从1开始），则有以下关系：

  • 当i>1时，节点i的双亲结点的编号为i/2（按照C++当中的除法，向下取整）。
  • 当2i <= N时，结点i的左孩子的编号为2i。
  • 当2i + 1 <= N时，结点i的右孩子编号为2i+1，否则无右孩子。

题解代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
using namespace std;
using ll = long long;
const int MAXN = 1e5+5;
ll tree[MAXN<<2], mark[MAXN<<2], A[MAXN], n, m;
//初始化线段树
//“根节点”坐标为1，tree[1]维护数组中[1, n]区间段的和
void build(int p=1, int l=1, int r=n){
    if(l == r) tree[p] = A[l];
    else{
        int mid = l+(r-l)/2;
        //左子树的区间大小等于右子树或者比右子树大1个,右边的区间可能要短一点！！
        build(2*p, l, mid);//左子树代表区间[l, mid]
        build(2*p+1, mid+1, r);//右子树代表区间[mid+1, r];
        tree[p] = tree[2*p] + tree[2*p+1];
    }
}
void push_down(int p, int len){
    tree[2*p] += (len-len/2)*mark[p];
    mark[2*p] += mark[p];
    tree[2*p+1] += len/2*mark[p];
    mark[2*p+1] += mark[p];
    mark[p] = 0;
}
//[l,r]：需要修改的区间，目标区间
//p：当前节点下标
//[cl, cr]：当前节点所对应的区间
ll query(int l, int r, int p=1, int cl=1, int cr= n){
    if(cr<l || cl >r) return 0;// 区间无交集. 剪枝
    else if(cl>=l && cr<=r) return tree[p]; // 当前节点对应的区间包含在目标区间中
     // 与目标区间有交集，但不包含于其中
    else{
        int mid = cl + (cr-cl)/2;
        push_down(p, cr-cl+1);//查询的时候先push_down应用到子节点，才能得到正确结果
        return query(l, r, 2*p, cl, mid)+query(l, r, 2*p+1, mid+1,cr);
    }
}

//d：元素增加量
void update(int l ,int r, int d, int p=1, int cl=1, int cr= n){
    if(cr<l || cl >r) return;
    else if(cl>=l && cr<=r){
        tree[p] += (cr-cl+1)*d;
        if(cr > cl) mark[p] += d; //叶子节点不能+=d，否则会一直累积
    } 
    else{
        int mid = cl + (cr-cl)/2;
        push_down(p, cr-cl+1);
        update(l, r, d, 2*p, cl, mid);
        update(l, r, d, 2*p+1, mid+1,cr);
        tree[p] = tree[2*p] + tree[2*p+1];
    }
}
int main(){
    while(cin >> n >>m){
        for(int i{1}; i<=n; ++i){
            cin >> A[i];//数组的坐标从1开始，否则需要改动build代码
        }
        build();
        while(m--){
            int o, p, q, r;
            cin >> o >> p >> q;
            if(o==1){
                cin >> r;
                //p, q对应的是A[p]-A[q];第p个数，即A[P]（在此题目中）
                update(p, q, r);
            }
            else cout << query(p, q)<<endl;
        }
    }
}

树状数组

学习视频：〔manim | 算法 | 数据结构〕 树状数组 | 支持多种动态维护区间操作 | bilibili(o゜▽゜)o☆(￣▽￣)”

题目：307. 区域和检索 - 数组可修改 | leetcode

设计一个可以单点修改，区间和查询。

树状数组：数组是从1开始的！！需要对应的二进制形式

需要对树状数组提前初始化，申请空间，因为add方法中有[ ]来快速访问数组。

需要实现三个方法：（这三个方法只针对树状数组，数组在另一个update中完成修改）

  • lowbit() //获取二进制的最后的”1“，比如11100，取最后的”1“，即100
  • add(int index, int 增量) //增加”增量“，初始化树状数组时，数组元素即为增量
  • ask() //查询前缀和

需要一个数组，来获得”增量“。（下面代码中的变量vtc）

在区间更改，单点查询中，也是用这些方法来完成对差分数组的前缀和计算，基于此去获取结果

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class NumArray {
public:
    NumArray(vector<int>& nums):vtc{nums},tree(nums.size()+1, 0) {//重要！需要先分配空间，因为add中要使用[]
        len = nums.size();
        for(int i{}; i<len; ++i){
            add(i, nums[i]);//树状数组初始化，从0至nums[i]；
        }
    }
    
    void update(int index, int val) { //将元素修改为val
        add(index, val-vtc[index]); //树状数组，对应位置，增加val-vtc[index]，是增量
        vtc[index] = val;
    }
    
    int sumRange(int left, int right) {
        return ask(right+1) - ask(left);//本应是right - (left-1)，避免判断left - 1>=0
    }
private:
    int len;
    vector<int> vtc;//需要vtc，用来计算增量值
    vector<int> tree;
    int lowbit(int x){
        return x&-x;
    }
    int ask(int pos){//本代码 输入的是index+1
        int ret{};
        for(int i{pos}; i>0; i-= lowbit(i)){
            ret += tree[i];
        }
        return ret;
    }
    void add(int index, int u){//本代码输入的是index
        for(int i{index+1}; i<=len; i+= lowbit(i)) tree[i] += u;//要index+1
    }
};