什么是二分答案

我们对于二分查找很熟悉，即在一个有序数据集上集中进行二分查找，换言之是在有序数组中快速查找某一个数。

而二分答案，则是已知答案在某一区间中，在这个区间中进行二分查找需要的答案。

欸 🤓☝️，这个时候我们还不知道答案是什么，于是我们需要为所有二分出来的数据点编写一个check函数，根据该函数返回的值，我们再来确定下一次二分的区间。

可以理解为更高效的枚举方式。

所以二分答案的难点与考点，就是如何确定答案范围，以及如何编写check函数

前缀和定义

前缀和就是从第一个数到当前数之间的区间的和。

？大概可以类比和函数的概念(S(x))。

这里给出在读取数据时直接计算前缀和的代码：

for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }

大致如此，这里 a[1]和是 s[1]需要在具体代码中确定

使用

• 以 o(1)的时间复杂度得到某块区间的总和

…

没了，
具体使用还是得在题目中体现，在一些需要快速计算子数组和、简化代码、区间查询的地方疑似很有用。