基础算法
快排调用
12sort(a, a + n); // 默认从小到大sort(a, a + n, cmp); // cmp是自定义比较函数
二分
1234567l = 0, r = n - 1;mid = l + r >> 1;对应 r = mid, l = mid + 1;mid = l + r + 1 >> 1;对应 r = mid - 1, l = mid;// 记忆:mid不加1,则l加1。
前缀和和差分
二维前缀和
123S[i, j] = 第i行j列格子左上部分所有元素的和以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
二维差分
比较巧妙:
如果q是全0的,那么其差分数组也是全0的,但实际上,q[i] = 0 +
q[i]。(所以就相当于对一个元素的小区域实现了加c(即q[i])的操作)
12345678910111213141516// 实现对数组q的一块矩形区域的每个元素 ...