基础算法
前缀和
一维
**原理:**利用\(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）、状态压缩（如用一个整数表示多个开关的状态）等。
按位与（&）
按位或（|）
按位异或（^）
//交换变量
a, b = 5, 7 # 二进制：a=0101，b=0111
a ^= b # a = 0101 ^ 0111 = 0010（2）
b ^= a # b = 0111 ^ 0010 = 0101（5）
a ^= b # a = 0010 ^ 0101 = 0111（7）
print(a, b) # 输出：7 5（交换成功）
//反转特定位
result = num ^ mask # 162 ^ 2 = 160（二进制10100000）
找规律
原理:
应用: