排序
快速排序
分治思想
思想解读：快速排序看左端点与右端点，双指针想法
首先将左边拿走，存起来为tmp，左边产生空位置。然后使用循环对右边指针进行判断，是否小于拿出的tmp，如果小于循环结束，将右边的值写到左边。再对左边指针循环，判断是否大于拿走的tmp，如果大于循环结束，把左边的值写到右边。然后两边进行递归排序。快排实际函数为partition函数返回分断点的下标。quick_sort只为递归调用
#代码模板：
import random
def partition(li, left, right):
tmp = li[left]
while left < right:
while left < right and li[right] >= tmp:
right -= 1
li[left] = li[right]
while left < right and li[left] < tmp:
left += 1
li[right] = li[left]
li[left] = tmp
return left
def quick_sort(li, left, right):
if left < right:
mid = partition(li, left, right)
quick_sort(li, left, mid - 1)
quick_sort(li, mid + 1, right)
li = list(range(1000))
random.shuffle(li)
print(li)
quick_sort(li, 0, len(li) - 1)
print(li)
归并排序
思想解读：
归并排序实际使用函数递归，以中间为界限，左右两边分别递归，使其有序（大的方向来讲）{细讲，在每次递归中其实都用到merge函数，先将其递归变为一个数，因为一个数是有序的，再使用merge函数进行归并}。然后在使用merge函数进行调整。merge函数的原理就是将数列分为两段，左右依次进行比较，谁小谁就被写入临时数组。
#代码模板：
import random
def merge(li, low, mid, high):
i = low
j = mid + 1
ltmp = []
while i <= mid and j <= high:
if li[i] < li[j]:
ltmp.append(li[i])
i += 1
else:
ltmp.append(li[j])
j += 1
while i <= mid:
ltmp.append(li[i])
i += 1
while j <= high:
ltmp.append(li[j])
j += 1
li[low:high+1]=ltmp
def mergrsort(li,low,high):
if low < high:
mid = (low+high)>>1
mergrsort(li,low,mid)
mergrsort(li,mid+1,high)
merge(li,low,mid,high)
li = [5,8,9,7,6,4,1,2,10]
print(li)
mergrsort(li,0,len(li)-1)
print(li)
二分
整数
整数二分背模板
注意：
- 考虑是否加1的问题
- 考虑左右等于mid是 加减问题
#代码模板：
q = [int(i) for i in input().split()]
x = int(input())
# 左红色部分的情况
l = 0
r = len(q) - 1
while l < r:
mid = l + r >> 1
if q[mid] <= x:
l = mid
else:
r = mid - 1
# 右绿色部分的情况
l = 0
r = len(q) - 1
while l < r:
mid = l + r + 1 >> 1
if q[mid] >= x:
r = mid
else:
l = mid + 1
数的范围 二分查找法
#解题答案：
n, m = map(int, input().split())
q = [int(i) for i in input().split()]
results=[]
while m:
x=int(input())
l = 0
r = n - 1
while l < r:
mid = (l + r) >> 1
if q[mid] >= x:
r = mid
else:
l = mid + 1
if q[l] != x:
results.append('-1 -1')
else:
results.append(l)
l = 0
r = n-1
while l < r:
mid = (l + r+1) >> 1
if q[mid] <= x:
l = mid
else:
r = mid - 1
results.append(l)
m -= 1
flag = 0
for result in results:
print(result, end=' ')
flag+=1
if flag == 2:
print()
flag = 0
# 6 3
# 1 2 2 3 3 4
# 3
# 4
# 5
浮点数
python不考虑
高精度
高精度加法
高精度减法
高精度乘法
高精度除法
在python中不考虑，在c中再考虑
前缀和
一维前缀和
注意：
- 前缀和的应用在于可以简化时间复杂度，例如求l到r区间内的和即求Sr-Sl-1之间的和。实际需要将整个数组进行遍历，时间复杂度为O(n),使用前缀和，时间复杂度为O(1)
- 前缀和初始化公式为s[i] = s[i-1] +a[i]
- 前缀和的部分求和公式为s[r] - s[l-1]
- 前缀和需要定义S0为0
在python中，定义舍弃下标为0的一维数组的方法：
a = [0]+[int(i) for i in input().split()]
s = [0]+[0]*n
可定义两个初始下标为1的一维数组
# 代码模板：
n, m = map(int, input().split())
a = [0]+[int(i) for i in input().split()]
s = [0]+[0]*n
for i in range(1,n+1):
s[i] = s[i-1] + a[i] # 前缀和的初始化
for i in range(m):
l, r = map(int, input().split())
print(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[x2] [y-1] - s[x1-1] [y2] +s[x1-1] [y1-1]
- 二维前缀和同样舍弃第0行第0列
在python中定义舍弃0行0列的二维数组方法：
n, m, q = map(int, input().split()) # m控制第一行的长度
a = [[0] for i in range(n)] # 每行前面加一列0
a.insert(0, [0] * (m + 1)) # 第0行插入m+1个0。
# 前面每行加入一列0，后面读入m列，所以每行有m+1列
for i in range(1, n + 1): # 从a[1][]开始，读矩阵
a[i].extend(map(int, input().split()))
s = [[0] * (m + 1) for i in range(n + 1)] # 初始化 n+1 行 m+1列的全0矩阵
# 代码模板：
n, m, q = map(int, input().split()) # m控制第一行的长度
a = [[0] for i in range(n)] # 每行前面加一列0
a.insert(0, [0] * (m + 1)) # 第0行插入m+1个0。
# 前面每行加入一列0，后面读入m列，所以每行有m+1列
for i in range(1, n + 1): # 从a[1][]开始，读矩阵
a[i].extend(map(int, input().split()))
s = [[0] * (m + 1) for i in range(n + 1)] # 初始化 n+1 行 m+1列的全0矩阵
for i in range(1, n + 1):
for j in range(1, m + 1):
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j] # 二维前缀和初始化
results = []
while q:
x1, y1, x2, y2 = map(int, input().split())
result = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] # 算子矩阵的和
results.append(result)
q -= 1
for k in results:
print(k,end=' ')
# 3 4 3
# 1 7 2 4
# 3 6 2 8
# 2 1 2 3
# 1 1 2 2
# 2 1 3 4
# 1 3 3 4
差分
一维差分
注意：
- 差分与前缀和为互反，类似于积分与微分。a数组为b数组的前缀和，b数组为a数组的差分。使用差分可降低时间复杂度
- ai = b1 + b2 + b3 + bi ……
- 使用差分无需构造a数组 ， 只需在 [1,1]区间 插入a1，[2,2]区间插入a2......
- 为a数组区间[l,r]中的每一个数加上一个c 只需要为bl 加上c br+1 减去c，就可实现该操作
# 代码模板：
n,m = map(int,input().split())
a=[0]+[int(i) for i in input().split()]
b=[0]+[0]*(n+1) # b数组定义时防止边界问题 ，多定义一个
def insert(l,r,c): # 重要的地方
b[l]+=c # 公式理解 a1 = b1 a2 = b1+b2
b[r+1]-=c # 1 1 a[1] -->b1 = b1+a[1] b2 = b2-a[1] 2 2 a[2] --> b[2] = b[2]+a[2]
for i in range(1,n+1):
insert(i,i,a[i])
while m:
l,r,c = map(int,input().split())
insert(l,r,c)
m-=1
for i in range(1,n+1):
b[i]+=b[i-1]
for i in range(1,n+1):
print(b[i],end=' ')
# 6 3
# 1 2 2 1 2 1
# 1 3 1
# 3 5 1
# 1 6 1
#
# 答案
# 3 4 5 3 4 2
二维差分
注意：
- 二维差分，在于假想数组b存在，使得a是数组b的前缀和
a[1][1] = b[1][1]
a[1][2] = b[1][1]+b[1][2]
n,m,q = map(int,input().split())
a = [[0] for i in range(n+1)] # 在每行前插入0
a.insert(0,0*(m+1)) # 在第一行插入m+1个0
for i in range(1,n+1): # 从a[1][]开始读入
a[i].extend(map(int,input().split()))
b = [[0]*(m+2) for i in range(n+2)] # 初始化 n+1行 m+1列 的全0矩阵
# b数组定义时 为防止边界问题 ，多定义一行一列 ，在c++中不存在这种问题
def insert(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 i in range(1,n+1):
for j in range(1,m+1):
insert(i,j,i,j,a[i][j])
while q:
x1,y1,x2,y2,c = map(int,input().split())
insert(x1,y1,x2,y2,c)
q-=1
for i in range(1,n+1):
for j in range(1,m+1):
b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]
for i in range(1,n+1):
for j in range(1,m+1):
print(b[i][j],end=' ')
print()
# 3 4 3
# 1 2 2 1
# 3 2 2 1
# 1 1 1 1
# 1 1 2 2 1
# 1 3 2 3 2
# 3 1 3 4 1
# 答案
# 2 3 4 1
# 4 3 4 1
# 2 2 2 2