基础算法

前缀和

一维

原理:利用\(s [i] = s [i-1] + a [i]\)求出任意区间 \([l, r]\) 的和，即 \(s [r] - s [l-1]\)

应用:快速求解数组中任意区间的和，例如在多次查询区间和的问题

二维

原理: 计算公式为\(s [i][j] = s [i-1][j] + s [i][j-1] - s [i-1][j-1] + a [i][j]\) 利用二维前缀和求出任意子矩阵的和，即 \(s [x2][y2] - s [x1-1][y2] - s [x2][y1-1] + s [x1-1][y1-1]\)

应用:快速计算二维数组中任意子矩阵的和

差分

一维差分

原理:对于一维数组 \(a [1...n]\)，构造差分数组 \(d [1...n]\)，使得 \(a [i] = d [1] + d [2] + ... + d [i]\)，即 \(d [1] = a [1]，d [i] = a [i] - a [i-1]（i≥2）\)。当需要对原数组的区间 \([l, r]\) 进行加 c 操作时，只需在差分数组中 \(d [l] += c，d [r+1] -= c（若 r+1≤n）\)，最后通过差分数组求前缀和即可得到更新后的原数组。

应用:高效处理数组的区间更新问题，当有大量区间更新操作时，使用差分可以将每次更新的时间复杂度降为 O (1)

二分

序列二分

原理:在有序序列中，通过不断将区间缩小为原来的一半，来查找目标元素。每次比较中间元素与目标元素的大小，确定下一步搜索的区间。

应用:在有序数组中查找元素是否存在、查找元素的第一个位置或最后一个位置等。

int binarySearch(int l, int r, int key) {
    int ret = -1;
    while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (arr[mid] < key) {
                l = mid + 1;
            } else if (arr[mid] > key) {
                r = mid - 1;
            } else {
                ret = mid;      // 记录位置
                r = mid - 1;  // 继续往左找
                //l =mid+1; 继续往右找
            }
        }
        return ret;
    }

答案二分

原理:将求解的问题转化为判断某个值是否满足条件，通过二分答案的可能范围，每次判断当前中间值是否满足条件，从而缩小答案的范围，直到找到满足条件的最小或最大值。

应用:求解满足某种条件的最优解问题，如求最小的满足条件的数值、最大的不满足条件的数值等。

static int find(int[] a, int n, int m) {
        int l = 1;
        int r = 1000000001; // 1e9 + 1，Java中直接使用整数常量

        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(mid, a, n, m)) {
                l = mid+1;
            } else {
                r = mid-1;
            }
        }
        return r;//一般情况是r  根据check定义
}

浮点数二分

原理:与整数二分类似，但由于浮点数的精度问题，需要设置一个足够小的精度范围（如 1e-8），当区间长度小于该精度时停止二分，取中间值作为结果。

应用:求解浮点数的方程根、求浮点数的极值等问题。

double l = 0, r = 1e9;
    while(r - l > eps){
        double mid =  (r + l) / 2;
        if(check(mid))
            l = mid;
        else
            r = mid;
    }
    printf("%.2f",l);
    return 0;

双指针

前后指针

原理:使用两个指针，一个从前向后遍历，一个从后向前遍历，根据题目条件调整指针的位置，从而解决问题。

应用:常用于数组或字符串的遍历问题，如判断回文字符串（一个指针从开头，一个从结尾，向中间移动比较字符）、数组中的元素配对问题等。

左右指针

原理:两个指针都从数组的一端（通常是左端）开始，向右移动，根据特定条件调整其中一个或两个指针的位置，以找到满足条件的区间或元素。

应用:求解滑动窗口问题（如最小覆盖子串）、有序数组中的和为目标值的元素对问题等。

位运算

原理:直接对整数在二进制层面上进行操作，包括与（&）、或（|）、异或（^）、左移（<<）、右移（>>）等操作。利用位运算可以高效地处理二进制位相关的问题。

应用:判断整数的奇偶性（通过判断最后一位是否为 1）、求一个数的二进制中 1 的个数、整数的快速乘除（左移相当于乘 2，右移相当于除以 2）、状态压缩（如用一个整数表示多个开关的状态）等。

找规律

原理:

应用: