二分查找
作用：查找一个有序数列中的某个符合要求的区间的某个边界，返回值为该数在数组中的下标
常用来寻找某个数，本身就是用二分查找的特性来寻找一个区间大小为1的区间，而该区间的左边界等于右边界等于该数在该数列的下标，故寻找数时没有很多限制条件。
整数二分示例：
bool check(int x) {/* ... */} // 检查x是否满足某种性质（认为含等于）
// 当check为true时要更新左边界的情况，注意，边界是一个确切的数，所以本质上还是在找数
int bsearch_right(int l, int r) //寻找某一区间左边界的模板
{
while (l < r)
{
int mid = l + r + 1 >> 1; // 让下取整变成上取整，避免l = mid出现死循环（更新含等于的判断语句中若更新的为l，则+1）
if (check(mid)) l = mid; // a[mid]满足左半边性质，应在[mid, r]继续寻找，由满足时更新l还是r来确定上一行和下一行的+1/-1
else r = mid - 1; // a[mid]不满足左半边性质，应在[l, mid - 1]继续寻找
}
return l; // 二分结束后，l == r。如果一定存在左半边的边界，l和r都是结果。如果不一定存在左半边的边界，需要做if判断
}
// 当check为true要更新右边界的情况
int bsearch_left(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // a[mid]满足右半边性质，应在[l, mid]继续寻找,如果查找左边界，则更新含等于的check决定更新r，查找右边界，则更新l（正好反过来）
else l = mid + 1; // a[mid]不满足右半边性质，应在[mid + 1, r]继续寻找
}
return l; // 二分结束后，l == r。如果一定存在右半边的边界，l和r都是结果。如果不一定存在右半边的边界，需要做if判断
}实数二分
简介：所谓实数二分，本质上是在数轴上取一个区间，求区间内某个符合我们要求的数，由于是在数轴上取数，所以实数二分具有稠密性，这就导致了该算法相对整数二分可以少判断许多的边界
代码示例
#include<iostream>
using namespace std;
int main(){
double a;
cin>>a;
double l=-10000,r=10000,mid; //由于是实数域，所有使用double
while(r-l>1e-8){ //由于稠密，所以r永远大于l，因此我们认为r和l之间的区间大小足够小时即为找到，一般这个足够小的区间长度为题目要求精度的基础上再乘10^-2
mid=(l+r)/2; //由于稠密，不可能存在边界卡死的情况，因此此处不用额外+1。double类型无法直接使用位运算
if(mid<=a) l=mid; //同样的，由于稠密，所以不用考虑那么多，直接等于mid即可
else r=mid;
}
printf("%.6lf",mid);
}二分的实际应用
我们的二分算法具有以下几个性质：
PS:二分性:对于给定区间,任意x属于该区间,均满足x右侧的部分满足一个与x相关的固定的关系式(check函数),x左侧的部分也 均满足一个固定的关系式,最常见的二分性就是单调性,对于单调递增,任意x,x左侧均小于x,x右侧均大于x
由此,如果我们发现题目要求我们找一个值,且该值在一个区间内,保证该区间具有二段性(此处的二段性一般为值的左侧全部不满足题目要求,值的右侧全部满足题目要求,我们需要跟据这个特点来编写我们的check函数),我们便可以使用二分算法在区间内寻找我们想要的这个数
我们的二分算法一般是用来优化我们的暴力枚举,我们已经得知原题目的答案一定在一个区间中,且该区间的元素具有上面描述的二分性,区间的边界就是我们要寻找的答案.那么此时我们其实就可以使用枚举法从左到右暴力枚举区间内所有数,进而得到第一个数(即题目要求的数).而这一个暴力枚举的过程,我们就可以使用二分去寻找,
归并排序
思想：
使用递归的方法将原数组切分成多个长度为2的数组（即最小单位数组），然后利用tmp数组将其在原位置上排好序，再返回到比最小单位数组大一点的数组，重新进行上述排序
int tmp[N]; // 归并步骤用
void merge_sort(int q[], int l, int r)
{
if (l >= r) return; //确定最小单位数组也包含两个元素
int mid = l + r >> 1;
merge_sort(q, l, mid); //将原数组分为以mid为界的两部分
merge_sort(q, mid + 1, r); //并分别进行递归
int k = 0, i = l, j = mid + 1; //此处k=0表示tmp数组会被多次利用，每次均从第0位用起
while (i <= mid && j <= r){ //此处使用了双指针算法，指针为i，j 此时将区间拆分为以mid为界的两部分，这两部分已经排好序，只要i和j均未出界便继续排
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];//q[i]象征当前单元的更小单元的前一个（以mid为界），q[j]象征更小单元的后一个，此时墙后两部分单元为排好的状态（因为递归，最后是两个元素的比较，其次均为两个有序数组的比较）
else tmp[k ++ ] = q[j ++ ]; //先将这两部分完成排序并放到tmp数组里面（此处tmp[k]一直在被赋值，所以tmp数组一直在更新中）
}
while (i <= mid) tmp[k ++ ] = q[i ++ ]; //此时i，j一定有一个出界了，然后将未出界的那部分直接搞到
while (j <= r) tmp[k ++ ] = q[j ++ ]; //看最后时i还是j没放完，将没放完的省的一点一次性放回去
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];//再将tmp数组中存的东西放回原数组的原位置
}
merge_sort(a, 0, n - 1); // 调用方法ps：在调用时后一位为数组最后一个元素的下标
拓展 ：分支思想
**概念：**将一个数组通过递归划分为多个小的区间，接着仅思考最小区间的情况，并将所有的小区间的答案合并后即为原问题答案
**案例：**求逆序对
const int N =1e5+10;
int arr[N],tmp[N];
long long merge_sort(int arr[],int l,int r){
if(l>=r) return 0; //当递归无法再进行下去时，返回0（表示结束，不再加数）
int mid=(l+r)/2; //通过mid将区间一分为2
int ans=merge_sort(arr,l,mid)+merge_sort(arr,mid+1,r);
int k=0,i=l,j=mid+1; //双指针算法进行寻找
while(i<=mid&&j<=r){ //当i或j一方出界后便立刻停止，在下方直接将剩余部分直接装汝tmp数组，注意，由于递归的原因，此时mid两边均以有序
if(arr[i]<=arr[j]) tmp[k++]=arr[i++]; //使用tmp数组进行存储，永远将大的放在前边
else{
tmp[k++]=arr[j++];
ans+=mid-i+1; //满足左侧大于右侧便增加ans，加的数为mid-i+1（表示该指针当前位置到mid有多少个数，由于左区间已排好，i从小到大移动，所以最小的数大于右侧j指向的数，则由该数到mid的所有数均大于右侧j指向的数）
}
}
while(i<=mid) tmp[k++]=arr[i++];
while(j<=r) tmp[k++]=arr[j++];
for(i=0,j=l;j<=r;i++,j++) arr[j]=tmp[i]; //将arr数组排好，保证后续递归仍然左右两侧均为有序的情况
return ans; //返回ans
}ps:由于递归从最小往回递归，所以每次都会返回当前区间逆序对的值并加给ans，而最小区间左右区间大小为1，因此左右区间逆序对数量为0（递归中最关键的一步），因此每回只用考虑左侧大于右侧的逆序对情况即可
快速排序
思想：
使用双指针算法进行指向，进而对数组内数据进行搜索，再将其切分为无数个小单元，在最小单元中进行交换(由于递归的特性，我们只需以最小层和最小层外的一层进行思考）
基本思路：
void quick_sort(int q[], int l, int r)
{
if (l >= r) return; //设置递归终点
int i = l - 1, j = r + 1, x = q[l + r >> 1];//设置分界点数字x，创建指针i，j，由于i，j起始时就需要++和--，所以最开始就要在两侧空出位置
while (i < j) //终止时j <= i
{
do i ++ ; while (q[i] < x); // 可换成 while(q[ ++ i ] < x);当左侧不满足小于x的条件时停止
do j -- ; while (q[j] > x); // 可换成 while(q[ -- j ] > x);当右侧不满足大于x的条件时停止
if (i < j) swap(q[i], q[j]); // 当i尚且小于j时二者才发生交换
}
quick_sort(q, l, j), quick_sort(q, j + 1, r); //排序完后在进入递归，对更小的单元进行排序，注意，此处此处的分界点不为l+r>>1，因为我们最后的分界点是x所在的位置，但x却不一定在原本的位置，因为我们已经在倒数第二轮将其调换过位置，且在循环的最后，一定存在j<=i&&arr[j]<=x&&arr[i]>=x，
}
quick_sort(a, 0, n - 1); // 调用方法延申：快速选择算法
作用：选择出一个无序数列中第n个小的数
int quick_search(int arr[],int l,int r,int k){
if(l>=r) return arr[k];
int i=l-1,j=r+1,x=arr[(l+r)/2];
while(i<j){
while(arr[++i]<x);
while(arr[--j]>x);
if(i<j) swap(arr[i],arr[j]);
} //模仿快排，在做完此步后前面的数已全部小于x，共j个
if(k<=j) quick_search(arr,l,j,k); //如果k<=j说明第k个数本身就小于x，所以在前半个区间找
else quick_search(arr,j+1,r,k); //不然第k个数就大于x，在后半个区间寻找，每次排序只用排一半的区间
}
int main() {
int n,m;
cin>>n>>m;
int arr[n+1];
for(int i=1;i<=n;i++){ //从第1个数开始输入，使下标与第下标个数同频（若题目存在第0个数这种说法，那就从0开始输入）
cin>>arr[i];
}
cout<<quick_search(arr,1,n,m);
}前缀和与差分
前缀和
前缀和含义：
对于给定的数组/矩阵，我们构建一个前缀和数组/矩阵，使得我们若要对原数组/矩阵的某一区间进行求和时，可以直接使用前缀和数组配合一个查询公式直接得到我们所要求的区间的和
前缀和解决的问题：
求出一个数组/矩阵要求的一个区间内所有数的和
一维前缀和
查询公式：
将数列依次输入到数组中，再将数组的每一项与前n项和相加，存在sum数组中，进而达到使得sum数组中存放了所有的前n项和
模板:
const int N = 1e5+10;
int a[N],s[N]; //定义出两个数组，分别用来存放数列与前缀和
int main(){
for(int i=1,i<=n;i++){ //特别注意，前缀和是从i=1时开始定义的，到i==n结束。该定义方式使得后面利用前缀和通项公式求前缀和和利用前缀和求某一区间的和的过程中不会出现边界问题。
cin>>a[i]; //输入原始数组
s[i]=s[i-1]+a[i]; //计算前缀和
}
int l,r;
cin>>l>>r; //给定所求区间的两个边界
cout<<s[r]-s[l-1]; //利用前缀和求给定区间的数之和的公式
}PS：
1.令s0=a0=0
2.复杂度由O(n)降为O(1) 3.数组a和S的第1个元素都不存储（下标为0），而从第2个元素开始存储（下标为1） 4.注意遍历范围是1 ~ n 5.在一些不涉及a[i]的题目中，不必要存储a[i]的值，只需要存储S[i]就足够。
二维前缀和
查询公式：
利用容斥原理对该区域内的所有数值进行求和
构建二维前缀和矩阵：
相较于一维前缀和的直接检查，我们的二维前缀和矩阵在创建时所表示的每一个数为其原矩阵对应位置左上角的所有数的和（如（3，4）则表示原矩阵从（0.0）到（3.4）的矩形区间内的所有数的和）
在此基础上我们才能使用前缀和矩阵对原矩阵某一区间进行求解
图解
求前缀和矩阵
求前缀和
模板：
const int N=1e5+10;
int a[N][N],sum[N][N];
int main(){
int a,n,m;
cin>>n>>m>>a; //假设给定一个n*m的数组，进行a次询问
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j]; //输入每个坐标对应的值
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]; //对i，j这个区间进行求和
}
}
for(int i=0;i<a;i++){
int x1,y1,x2,y2; //假设下x1,y1为给定区间左上角的点x2,y2为给定区间右下角的点
cin>>x1>>y1>>x2>>y2;
cout<<sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]; //对给定区间进行求和
//因为（x1,y1）在我们的要求区间内，所以我们要减掉的内容始终为x1-1/y1-1
}
}PS：
1.对于sum数组与a数组，二者的i，j一者为0时，其数组元素对应的值为0。
2.注意循环从1开始，到n结束
3.类比一维的前缀和，我们的二维前缀和在减掉边界时也要在原边界的基础减一再减（即最后一行在输出时对x1,y1的减一）
差分
所谓差分，即是在给出前缀数组的情况下求原始数组。
那么我们求差分的意义是什么？
首先，我们要明确一件事，那就是任意一个数组都可以是前缀和数组
证明：
前缀和数组中第i个数表示数组0到i的所有数之和，那么第只要a[i]=s[i]-a[i-1],若我们默认a[0]=0，那么我们便可以得到任何一个数组的原数组a[i]，而这个数组就是我们所要求的差分数组
那么我们求差分数组的意义是什么呢？
首先我们来看这么一道题
给定区间[l, r ]，让我们把a数组中的[l, r] 区间中的每一个数都加上c,即 a[l] + c , a[l + 1] + c , a[l + 2] + c ,,,,,, a[r] + c;
暴力做法是for循环l到r区间，时间复杂度O(n)，如果我们需要对原数组执行m次这样的操作，时间复杂度就会变成O(n * m)。有没有更高效的做法吗?
考虑差分做法，(差分数组派上用场了)
首先，我们知道，a数组一定是一个前缀和数组，而凡是前缀和数组就一定有差分数组。
由前缀和的特性可知，如果我们想要让一个区域（【l,r】）的数加上同一个数x，只需要让原数组a[l-1]+x,再让a[r+1]-x即可。由此我们就对原数组实现了在[l,r]的区域全部加上一个x的操作
即：
首先让差分b数组中的 b[l] + c ,通过前缀和运算，a数组变成 a[l] + c ,a[l + 1] + c,,,,,, a[n] + c;
然后我们打个补丁，b[r + 1] - c, 通过前缀和运算，a数组变成 a[r + 1] - c,a[r + 2] - c,,,,,,,a[n] - c;
所以我们不难看出，前缀和的作用是求一串数字中一个区间内所有数的和，而差分数组的作用则是优化对一个区间内所有的数同时加减一个数的操作
同样的，差分数组求前缀和得到前缀和数组（要被执行区间内加一个数的数字），前缀和数组求差分得到差分数组（前缀和的原数组）
一维差分
原理
对于给定区间[l, r ]，让我们把a数组中的[l, r] 区间中的每一个数都加上c,即 a[l] + c , a[l + 1] + c , a[l + 2] + c ,,,,,, a[r] + c;
暴力做法是for循环l到r区间，时间复杂度O(n)，如果我们需要对原数组执行m次这样的操作，时间复杂度就会变成O(n * m)。有没有更高效的做法吗? 考虑差分做法，(差分数组派上用场了)。
始终要记得，a数组是b数组的前缀和数组，比如对b数组的b[i]的修改，会影响到a数组中从a[i]及往后的每一个数。
首先让差分b数组中的 b[l] + c ,通过前缀和运算，a数组变成 a[l] + c ,a[l + 1] + c,,,,,, a[n] + c;
然后我们打个补丁，b[r + 1] - c, 通过前缀和运算，a数组变成 a[r + 1] - c,a[r + 2] - c,,,,,,,a[n] - c;
由此我们可以得到一维前缀和数组的构造公式
b[i] = a[i] - a[i - 1];（i从1开始到等于a的长度结束）
题目练习： AcWing 797. 差分
输入一个长度为n的整数序列。 接下来输入m个操作，每个操作包含三个整数l, r, c，表示将序列中[l, r]之间的每个数加上c。 请你输出进行完所有操作后的序列。
输入格式 第一行包含两个整数n和m。 第二行包含n个整数，表示整数序列。 接下来m行，每行包含三个整数l，r，c，表示一个操作。
输出格式 共一行，包含n个整数，表示最终序列。
代码实现
#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 = 1;i <= n; i++)
{
scanf("%d", &a[i]);
b[i] = a[i] - a[i - 1]; //构建差分数组
}
int l, r, c;
while(m--)
{
scanf("%d%d%d", &l, &r, &c);
b[l] += c; //表示将序列中[l, r]之间的每个数加上c
b[r + 1] -= c;
}
for(int i = 1;i <= n; i++)
{
b[i] += b[i - 1]; //求前缀和运算
printf("%d ",b[i]);
}
return 0;
}PS;
差分操作使时间复杂度由O(n)转变为O(1)
二维差分
对于二维前缀和，他只然也有自己的构造公式
b[i] [j] = a[ i ] [ j ] − a[i − 1] [ j ] − a[ i ] [ j − 1] + a[i −1 ] [j − 1]（i j 均从1开始到等于结束）
原理：
对于前缀和数组 若我们像要求一个位置上具体的值，只要让前缀和数组中求前缀和的公式的x2，y2变为1即可，因此也就得到了上述公式
代码实现：
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e3 + 10;
int a[N][N], b[N][N];
int main()
{
int n, m, q;
cin >> 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++)
{
b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]; //构建差分数组
}
}
while (q--)
{
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += 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]);
}
printf("\n");
}
return 0;
}位运算
：位运算进行的虽然是二进制运算，但其最后的结果为十进制结果要点：
1.x & -x返回最后1位1，例如101000返回1000
int lowbit(int x) {
return x & -x;
}应用：计算一个十进制数的二进制表示中1的个数
代码实现
#include <iostream>
using namespace std;
int lowbit(int x){
return x&(-x+1);
}
int main(){
int x;
cin>>x;
int res=0;
while(x){
x-=lowbit(x);
res++;
}
cout<<res;
}2.x >> k && 1返回x右起第k位二进制数 (注意，此处的第k位是从0开始)
模板：
int main(){
int 10;
for(int i=3;i>=0;i++) cout<<(n>>k&1); //从大到小即按原位输出
}说明：
1.若让x不停地减去最后1位1，直到变成0，做减法的次数就是x二进制表示的1的个数
2.可用for(int k = 31; k >= 0; k--)把int转成二进制数
离散化
概念
题目给出一个大的区间，但只需要对里面的部分数进行操作，这时我们就会使用离散化操作来减小代码所申请的内存
思想
需要将题目中提供的数据进行映射，即将原数轴上的数放在新的数轴上，且在新数轴上的x表示该数的映射值，y表示该数的原值。
常见疑问
1.为什么要去重？
因为去掉重复的原始下标便于二分查找，二分查找需要数组中元素按照从小到大排序，且尽可能没有重复。
2.去重不会有问题吗
不会。一定要切记，删除的是原数组上相同的下标，而不是原数组上相同的元素。all数组中存放的是原数组下标，其本身下标表示映射下标，在查找add.first时，查找的为元素的原始下标，返回为元素的映射下标，本身所有被提问到的元素数量未发生变化，所以不会有任何影响。
例题：
代码实现
#include <iostream>
#include <vector>
#include <alogrithm>
using namespace std;
using PII=pair<int,int>; //创建pair结构，using类似于c中的define
const N=3e5+10; //n+2m n表示所有相加的数据，极限情况为全部加在不同的位置上，此时数据至多为n个，m表示假设提问全部的l和r，只有n+m才能保证a数组包含all中全部的下标
int a[N],s[N]; //求前缀和常用的数组
vector<int> all; //用于存放提问与不为0的全部下标
vector<PII>query,add; //query用于存放提问的数据，add用于存放每回加的数据
int find(int x){ //经典的二分查找，用于查找映射下标。切记：二分查找查找的是元素，返回的是下标
int l=0,r=all.size-1; //定义双边界
while(l<r){
int mid=l+r+1>>1; //这里查找的区间大小为1，所以用查找左右边界中的任何一个都可以
if(all[mid]<=x) l=x;
else r=mid-1
}
return l+1; //由于我们前缀和从1开始，所以我们返回的下标+1
}
int main(){
int n,m;
cin>>n,m;
for(int i=0;i<n;i++){
int x,y;
cin>>x,y;
add.push_back({x,y});
all.push_back(x);
}
for(int i=0;i<m;i++){
int l,r;
cin>>l>>r;
query.push_back({l,r});
all.push_back(l), all.push_back{r}; //询问的数据也要存放在all中，因为会有0的存在，元素组中不同位置的0也要存放在all中不同的位置上
}
sort(all.begin,all.end); //将all数组进行排序，便于后续二分查找，由于all中元素记录的是下标，且理应是从小到大的顺序，而我们的映射同样也是从小到大映射，所以应该进行排序
//此时我们可以看出，all数组自身的下标记录的是原下标的映射下标，记录的元素为原下标
add.erase(unique(all.begin(),all.end()),all.end());//删除all中重复的数据，由于all中存放的是下标，所以我们删的是重复下标，总元素格未发生变化
for(int i=0;i<n;i++){ //n次相加操作
int x=find(add[i].first) //查询add的每一次的下标所对应的映射下标
a[x]+=add[i].second //a本身代表映射数组，将数据赋值给映射数组的位置上
}
for(int i=1;i<=all.size;i++) s[i]=s[i-1]+a[i]; //计算前缀和，注意<=，因为我们的前缀和从1开始，所以末尾下标也要+1，all的数组长度即是映射下标的总数
for(int i=0;i<m;i++){
int l=query.first,r=query.second;
cout<<s[r]-s[l-1]<<endl; //查询区间内的和
}
}