题目来自Acwing 网站，该专栏为博主在ACWing算法基础课上的学习记录和总结。

排序

基础算法模板题（一）—— 排序

二分和前缀和

二分

求红色部分的右边界

int l = 0, r = n-1;
while(l < r ){int mid = l + r + 1 >>1;if(check(红色性质是否满足)) l =mid;else r = mid -1;
}

这里mid之所以要加上1，是当区间长度为2时，分区一直没有变化，陷入递归死循环。
比如l = r - 1时， mid = (r - 1 + r)/2 = r - 1，如果此时刚好满足红色性质，那么mid会始终等于r - 1，分区一直没有变化，陷入递归死循环。
而加了1之后变成上取整 mid = r，就有机会break掉了。

求绿色部分的左边界

int l = 0, r = n-1;
while(l >  r){int mid  = l + r >> 1;if(check(绿色性质是否满足)) r = mid;else l = mid + 1;
}

前缀和

一维前缀和

S[i] = a[1] + a[2] + … a[i]
a[l] + … + a[r] = S[r] - S[l - 1] = S[r]-S[l]+a[l]

二维前缀和

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]

基础算法模板题（二）—— 二分

差分

一维差分

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

对于数组a[i] = b[1] + b[2 ]+ b[3] +…… + b[i]

则a数组是b数组的前缀和数组，b数组叫做a数组的差分数组。差分数组为：
b[0] = a[0 ]= 0;

b[1] = a[1] - a[0];

b[2] = a[2] - a[1];

b[3] =a [3] - a[2];

…

b[n] = a[n] - a[n-1];

有了差分数组b，通过前缀和运算，就可以在O(n) 的时间内得到a数组。给定数组a，对a数组[l,r]区间中的每一个数加上c，常规做法是循环l到r加上c。执行m次操作，时间复杂度就为O(n*m)。

对于这个问题，就可以使用差分数组了：
给a数组中的[ l, r]区间中的每一个数都加上c,只需对差分数组b做 b[l] + = c, b[r+1] - = c。时间复杂度为O(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

基础算法模板（三）—— 差分和前缀和

双指针算法

双指针常见由以下两种：第一种是在两个不同序列中扫描，比如归并排序的合并两个有序序列为一个序列。 第二种是在同一个序列中一前一后扫描，比如快速排序的partition函数。

模板

for(int i = 0, j =0; i < n; i++){while(j <= n&& check(j,i) )j++;题目逻辑处理代码;
}

思想

使用双指针算法可以将常规的双重循环O(n^2)复杂度，根据题目给的某种性质（通常是单调性）使得两个指针由于一定的制约关系都只用遍历一遍整个区间，从而达到将O(n ^2)种状态优化为O（n）种组合状态。所以虽然是双重for循环，但是扫描的次数不超过O(2n)，从而将复杂度优化为O(n)。

例如，每个单词以空格隔开，要求每一行输出一个单词。输入：abc def ghijkl mn，输出：
abc
def
ghijkl
mn

import java.util.Scanner;
class Main{public static void main(String args[]){Scanner reader = new Scanner(System.in);String s = reader.nextLine();int n = s.length();for(int i = 0; i < n; i++){//j指针寻找单词的最后一个字符int j = i;while( j < n && s.charAt(j) != ' ') j ++;//[i,j)为一个单词for(int k = i; k < j; k ++) System.out.print(s.charAt(k));System.out.println();i = j; //i指向j}}
}

基础算法模板题（四）——双指针

位运算

得到x的二进制表示的第k位： x>> k & 1
lowbit(x) 返回x二进制表示的最后一位1：x & -x

DFS

DFS算法就像一个执着的人，一条路走到 黑，走不通才会退到上一个路口走另一条。dfs通常不需要构建栈结构，利用函数递归调用即可实现。递归函数的调用本身就构建好了栈。我们所需要的是保存每一条路径上的状态。在这一过程中经常需要用到 剪枝 和 回溯策略。
同时DFS也不具有最短性质。该算法本质是暴力 枚举完所有可能状态（方案），找到合适的解。空间复杂度是O(树的高度)

基础算法模板题（五）—— DFS