1. Quick sorting( Acwing 785. Quick sort)

void quick_sort(int a[],int l,int r)
{
  if(l>=r)return;
  int i=l-1,j=r+1,x=l+r>>1;//'+' takes precedence over '>' shift operator
  while(i<j)
  {
    do i++;while(a[i]<x);
    do j--;while(a[j]>x);
    if(i<j) swap(a[i],a[j]);
  }
  quick_sort(q,l,j);
  quick_sort(q,j+1,r);
}

Analysis:
1. Set an X to divide the array into two arrays;
2. Set two pointers i and j close to each other from both ends of the head and tail respectively, and put the data smaller than x on the left side of X, and the data larger than x on the right side of X. When the two hands meet, continue to the next step;
3. Continue the above operations with the data on the left and the data on the right;
4. Repeat the above process, and it can be seen that this is a recursive process; when the data on the left and right sides are in order, the whole array will be in order naturally.

2. Merge and sort Acwing 787. Merge sort

void merge_sort(int a[],int l,int r)
{
  if(l>=r)return;
  int mid=l+r>>1;
  merge_sort(a,l,mid);
  merge_sort(a,mid+1,r);
  int k=0,i=l,j=mid+1;
  while(i<=mid&&j<=r)
  {
    if(q[i]<q[j])tmp[k++]=q[i++];
    else 
      tmp[k++]=q[j--];
  }
  while(i<=mid)tmp[k++]=q[i++];
  while(j<=r)tmp[k++]=q[j--];
  for(int i=l,k=0;i<=r;i++)
    q[k++]=tmp[i++];
}

3. Integer binary algorithm template Acwing 789. Number range

bool check(int x)
{
  /* ... */
}//Check whether x satisfies certain properties
//Use when the interval [l,r] is divided into [l,mid] and [mid+1,r]
int bsearsh_1(int l,int r)
{
  while(l<r){
    int mid=l+r>>1;
    if(check(mid))r=mid;
    else l=mid+1;
  }
  return l;
}
//Use when the interval [l,r] is divided into [l,mid-1] and [mid,r]
int bsearsh_2(int l,int r)
{
  while(l<r){
    int mid=l+r+1>>1;
    if(check(mid))l=mid;
    r=mid-1;
  }
  return l;
}

4. Floating point binary template The cubic root of Acwing 790

bool check(int x)
{
  /*  */
}//Check whether x obeys certain properties
double bsearsh(double l,double r)
{
  const double e=1e-6;
  while(l<r)
  {
    double mid=(l+r)/2;
    if(check(mid)) r=mid;
    else l=mid;
  }
  return l;
}

5. High precision addition Awcing 791. High precision addition

//C=A+B,A>=0,B>=0
vector<int>add(vector<int> &A,vector<int> &B)
{
  if(A.size()<B.size()) return add(B,A);
  int t=0;
  vector<int> C;
  for(int i=0;i<A.size();i++)
  {
    t+=A[i];
    if(i<B.size())t+=B[i];
    C.push_back(t%10);
    t/=10;
  }
  if(t)C.push_back(t);
  return C;
}  

6. High precision subtraction Acwing 792. High precision subtraction

//C=A-B,A>=B,A>=0,B>=0
vector<int>sub(vector<int> &A,vector<int> &B)
{
  if(A.size()<B.size()) return sub(B,A);
  vector<int> C;
  for(int i=0,t=0;i<A.size();i++)
  {
    t=A[i]-t;
    if(i<B.size())t-=B[i];
    C.push_back(t+10%10);
    if(t<0) t=1;
    else t=0;
  }
  while(C.size()>1&&C.back()==0)C.pop_back();//Remove leading 0
  return C;
}  

7. High precision multiplied by low precision Acwing 793. High precision multiplication

//C=A*b,A>0,b>0
vector<int>mul(vector<int> &A,int b)
{
  vector<int> C;
  int t=0;
  for(int i=0;i<A.size()||t;i++)
  {
    if(i<A.size())t+=b*A[i];
    C.push_back(t%10);
    t/=10;
  }
  return C;
}  

8. High precision divided by low precision Acwing 794. High precision Division

//C=A*b,A>0,b>0
vector<int>div(vector<int> &A,int b)
{
  vector<int> C;
  int r=0;
  for(int i=A.size()-1;i>=0;i--)
  {
    r=r*10+A[i];
    C.push_back(r/b);
    r%=b;
  }
  reverse(C.begin(),C.end());
  while(C.size()>1&&C.back()==0)C.pop_back();
  return C;
}  

9. One dimensional prefix and Acwing 795. Prefix and

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

10. Two dimensional prefix and Acwing 796. Sum of submatrix

S[i,j] = sum of all elements in the upper left part of column j of row i
 Taking (x1,y1) as the upper left corner and (x2,y2) as the lower right corner, the sum of submatrixes is:
S[x2,y2]-S[x1-1,y1-1]+S[x2,y1-1]+S[x1-1,y1-1]

11. One dimensional difference Acwing 797. Differential

Add c:B[l]+=c,B[r+1]-=c to each number in the interval [l,r]

12. Two dimensional difference Acwing 798. Difference matrix

Given that (x1,y1) is the upper left corner, (x2,y2) is all elements in the submatrix of the lower right corner plus c:
S[x1,y1]+=c,S[x2+1,y1]-=c,S[x1,y2+1]-=c,S[x2+1,y2+1]+=c

13. bit operation Acwing 801. Number of 1 in binary

Find the number k of N: n > > K-1
 Returns the last bit of N: lowbit (n) = n & - n

14. Double pointer algorithm Acwing 799. Longest continuous disrepeat subsequence，Acwing 800. Target and

for(int i=0,j=0;i<n;i++)
{
  while(j<i&&check(i,j)) j++;
  //The logic of specific problems
}
Common classification questions:
    (1) For a sequence, maintain an interval with two pointers
    (2) For two sequences, maintain a certain order, such as merging two ordered sequences in merge sort

15. discretization Acwing 802. Interval and

vector<int> alls;//Store all values to be discretized
sort(alls.begin(),alls.end());//Sort all values
alls.erase(unique(alls.begin(),alls.end()));//Remove duplicate elements

//Bisection to find the value of x corresponding to discretization
int find(int x)//Find the first position greater than or equal to x
{
  int l=0,r=all.size()-1;
  while(l<r)
  {
    int mid=l+r>>1;
    if(alls[mid]>=x)r=mid;
    else  l=mid+1;
  }
  return r+1;//Map to 1, 2,... n
}

16. Interval consolidation Acwing 803. Interval merging

//Merge all intervals with intersection
typedef pair<int, int> PII;
void merge(vector<PII> &segs)
{
  vector<PII> res;
  sort(segs.begin(),segs.end());
  int st=-2e9,ed=-2e9;
  for(auto seg:segs)
    if(ed<seg.first)
  {
    if(st!=-2e9)  res.push_back({st,ed});
    st=seg.first,seg.second;
  }
  else
    ed=max(ed,seg.second);
  if(st!=-2e9)res.push_back({st,ed});
  segs=res;
}