T1前缀和

前缀和是指在同一个数组中，从第一个元素开始，到当前元素中间的所有元素之和。

公式：s[i]=s[i-1]+a[i]。

理解：s这个数组的最后一位，是a数组所有的数字之和，例如a数组有1 2 3 4 5 6这几个数，那么s数组的末尾就是1+2+3+4+5+6=21，s数组的末尾就是21。

示例代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n, m, l, r;
int a[N], sum[N];

int main() {
	cin >> n >> m;
	for (int i=1; i<=n; i++) {
		cin >> a[i];
		sum[i] = sum[i-1]+a[i];
	}
	while (m--) {
		cin >> l >> r;
		cout << sum[r]-sum[l-1] << '\n';
	}
	return 0;
}

例题：前缀和

题目描述：输入一个长度为 n 的整数序列。接下来再输入 m 个询问，每个询问输入一对 l,r。 对于每个询问，输出原序列中从第l个数到第 r个数的和。

思路：定义前缀和数组sum，计算前缀和，while循环输入要输出的位置。

T2双指针

双指针指左右指针和快慢指针两种。

左右指针：指针分别从数组的左边和右边向中间推进，需要判断数组是否满足一些特定的条件，如果满足，那么输出数据，否则继续移动。

快慢指针：指两个指针都从起点出发，一个指针每次循环都要向前移动，还有一个指针只有当一些特定的条件满足后才会移动。

双指针可以将一个时间复杂度为$O(n^2)$的代码优化到O(n)。

样例代码：

左右指针：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N],m,maxn;
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int w=0,ans=0,i=0,j=n-1;
	while(i<j){
		w=min(a[i],a[j])*(j-i);
		ans=max(ans,w);
		if(a[i]<=a[j]){
			i++;
		}else{
			j--;
		}
	}
	cout<<ans;
	return 0;
}

示例题：乘最多水的容器

题目描述：给定一个长度为n(2≤n≤$10^5$) 的整数数组ℎ(0≤ℎ[i]≤$10^4$)。有n条垂线，第i条线的两个端点是(i, 0)和(i, h[i])。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量m。

思路：让i在最左边，j在最右边，去寻找最大面积，定义w取a[i],b[j]的最小值，定义ans为最终输出结果，w和max之间取最大值输出。

快慢指针：

例题：判断子序列

题目描述：给定一个长度为n的整数序列a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm。请你判断 a序列是否为 b序列的子序列。子序列指序列的一部分项按原有次序排列而得的序列，例如序列 a1,a3,a5 是序列 a1,a2,a3,a4,a5 的一个子序列。

定义i和jwhile循环判断，如果b[j]=a[i]说明它是b[j]的子序列，如果i=n说明a所有的数都是b的子序列。

#include<iostream>
using namespace std;

const int N = 1e5 + 10;
int a[N], b[N]; 

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < m; i++) cin >> b[i];
	
	int i = 0, j = 0;
	while (i < n && j < m)
	{
		if (b[j] == a[i]) i++, j++;
		else j++;
	}
	if (i == n) cout << "Yes";
	else cout << "No";
	return 0;
}

T3位运算

位运算符：&

&：如果有一个0，那么就是0，如果所有的全是1，那么就为1。

|：如果有一个1，那么就是1，如果所有的全是0，那么就为0。

^如果相同为0，不同为1。

<<左移位，左移多少位，就在低位补多少个0。

x<<i相当于x*$2^i$。

>>右移位，右移多少位，就在低位补多少个0。

x>>i相当于x/$2^i$。

T4原码，补码，反码

原码：指一个整数的二进制就是它的原码。

补码：正数的补码等于它的二进制本身，负数的补码等于它的二进制+1。

反码：正数的反码等于它的原码，负数的补码等于他的除符号外所有二进制数的所有数字的取反。

T5差分

差分指a，b两个数组，如果a数组是b数组的前缀和，那么，b数组就是a数组的差分数组。

差分和前缀和是相反关系。

示例代码：

int n, q, a[100010], b[100010];
int main() 
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) b[i] = a[i] - a[i - 1]; // 构造a的差分数组b
    while (q--)
    {
        int l, r, c;
        cin >> l >> r >> c;
        b[l] += c;   // 操作差分数组b
        b[r + 1] -= c;
    }
    for (int i = 1; i <= n; i++) b[i] += b[i - 1], cout << b[i] << " "; // 对b求前缀和得到修改后的a
    return 0;
}