1.前缀和

1.定义

假设有一个数组a[n],要计算它的前j个元素的和为

a[0]+a[1]+...+a[j-1]

时间复杂度为O(j)，且随着j的变大时间复杂度越来越大。

使用了前缀和算法则为

sum[j]-sum[j-1]

时间复杂度是O(1)，且数据越大优势越明显。

2.例题一

详解见《可获得的最小取值》详解

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 200010;
long long a[N], sum[N];
int main()
{int n, k;cin >> n >> k;for (int i = 0; i < n; i++){cin >> a[i];}sort(a, a + n);for (int i = 1; i <= n; i++)//sum的下标表示的是前几位的和，所以i不能从0开始，否则sum会越界{sum[i] = sum[i - 1] + a[i-1];}long long ans = 1e18;for (int p = 1; p <= k; p++)//i初值为1的道理与上相同{ans = min(sum[n] - sum[n + p - k] + sum[2 * p], ans);}cout << ans;return 0;}

3.例题二

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N =100005;
long long a[N], sum[N];
int main()
{//long long int x=0;//存储最终结果int n;cin >> n;for (int i = 0; i < n; i++){cin >> a[i];}for (int i = 1; i <= n; i++){sum[i] = sum[i - 1] + a[i-1];}long long int ans = 1e18;for (int i = 0; i < n; i++)//去掉=，省下一次计算量{ans = min(max(sum[i],(sum[n]-sum[i])),ans);}cout << ans;
}

4.例题三

异或：相同为0，不同为1