前缀和

前缀和 指一个数组中，从第一个元素开始，到当前元素为止的所有元素之和。

前缀和和定义

给定数组 a=[$a1,a2,a3......,an$]

我们定义$si=a1+a2+a3+...+ai$

那么由$si$构成的数组 s=[$s1,s2,s3,...,si,si+1,...,sn$]

推导：

$sum[1]=a[1]$

$sum[2]=a[1]+a[2]$

$sum[3]=a[1]+a[2]+a[3]$

. . .

$sum[i]=a[1]+a[2]+a[3]...+a[i]=sum[i-1]+a[i]$

差分

​差分数组的概念​： 设有 ， 两个数组，若 数组为 数组的前缀和数组，我们则称 数组为 数组的差分数组。差分和前缀和是相反的关系。

根据前面学习的前缀和数组和原数组的关系：$a[i]=a[i-1]+b[i] b[i]=a[i]-a[i+1]$即差分数组的第i项等于原数组的第 i项和第i-1项的差，对差分数组求前缀和，即得到了原数组。

双指针

双指针算法是一种入门级算法，这里的指针并不是C语言里面用来保存地址的指针，而是用来遍历扫描序列或者数组的下标，可以简单理解为循环变量i或j。

双指针算法可以分为两大类别： 第一类：两个指针指向同一序列，如冒泡、选择、插入等排序算法其实都是双指针。 第二类：两个指针分别指向不同序列，如归并排序的归并过程。

双指针按特点可以分成两类：左右指针，快慢指针

位运算

1：按位与 &  有0则0，全1为1. 2）

2：按位或 |  有1则1，全0为0. 3）

3：按位取反 ~  1变0，0变1. 4）

4：按位异或 ^  相同为0，不同为1. 5）

5：左移位 <<  左移多少位，就在低位补多少个0. x << i相当于 𝑥∗2𝑖x∗2i 6）

6：右移位 >>  右移多少位，就在高位补多少个0，并删除多少个低位. x >> i相当于 𝑥/2𝑖x/2i

二进制数的原，反，补码

​原码​： 将一个整数转换为二进制表 如a = -8，它的原码就是1000 0000 0000 1000，原码就是一个整数原本的二进制形式。

​反码​： 正数的反码等于它的原码，​负数的反码是将其原码除符号位外所有位取反​，如 a = -8，其反码是1111 1111 1111 0111。

​补码​： 正数的补码等于它的原码，​负数的补码等于它的反码+1​，如 a = -8，其原码是1000 0000 0000 1000，反码是1111 1111 1111 0111，补码是1111 1111 1111 1000。