前缀和

a[5] = {5, 1, 4, 3, 9};

普通数组中，每个元素只表示自己。
如果要求一段区间的和，只能把区间里的数一个个加起来。

如果查询很多次，这显然会产生大量重复计算。

于是我们提前记录前缀和：

a =  5  1  4   3   9
s =  0  5  6  10  13  22

其中 s[i] 表示原数组前 i 个元素之和。

要求 [l,r] 的区间和，只需要：

例如原数组下标 [2,4]：

前缀和预处理复杂度为 $O(n)$，之后每次区间查询只需要 $O(1)$。

它的本质是：

提前保存已经计算过的信息，避免以后重复计算。

二分

b[5] = {1, 3, 4, 4, 9};

如果数组无序，要寻找一个数 x，通常只能一个个比较，最坏复杂度为 $O(n)$。

但有序数组不同。

假设我们检查中间位置 b[m]：

• 如果 x < b[m]，那么 m 右边所有数都不可能是答案；
• 如果 x > b[m]，那么 m 左边所有数都不可能是答案；
• 如果相等，直接找到。

所以一次比较就能排除大约一半元素。

搜索范围不断变成：

n → n/2 → n/4 → n/8 → ...

因此二分的时间复杂度为：

常用模板：

int l = 0, r = n - 1;

while (l <= r) {
    int m = l + (r - l) / 2;

    if (b[m] == x) break;

    if (b[m] < x)
        l = m + 1;
    else
        r = m - 1;
}

二分真正重要的不是模板，而是：

为什么根据当前信息，可以确定其中一半绝对没有答案。

前缀和和二分虽然用途不同，但都有一个共同点：

利用数据之间的结构，减少重复工作。