普及组基础算法

这些都是零零散散接触过的基础算法，写个笔记把这些整理到一起来。

线性降维技巧

之前在学校洛谷团队里看到一个题单，觉得这些技巧可能有用，就转存了。

前缀和 差分

前缀和是一种对区间求和问题进行降维的方法。具体地，对于给定数组 \(A[n]\)，求出 \(A[l,r]\) 区间和这个问题，朴素的方法时间复杂度为 \(O(n)\)，使用前缀和进行一次 \(O(n)\) 的预处理后，可以 \(O(1)\) 进行查询。
实现方法：

int n;
int a[100],f[100]; // f[]为预处理数组，f[i]表示a[1]到a[i]的和

cin >> n;
for (int i=1;i<=n;i++){
    cin >> a[i];
    f[i]=f[i-1]+a[i]; // 预处理：前缀和的递推计算方法
}

// 查询：a[l,r]的和是：f[r]-f[l-1]