返回学习页
知识点指南
Prefix Sums
Prefix sums store cumulative totals. Once built, the sum of a range can be found by subtracting two stored totals.
什么时候使用
读题时可以留意这些信号。
- The task asks for many interval totals.
- You need repeated totals over consecutive positions.
- The values are fixed while queries are answered.
常见错误
提交前可以检查这些小陷阱。
- Mixing inclusive and exclusive endpoints.
- Forgetting the initial zero.
- Using prefix sums when values change and no update structure is provided.
怎么写成代码
把知识点翻译成变量、循环、判断和更新。
- Make prefix[0] = 0.
- Build prefix[i + 1] = prefix[i] + values[i].
- For a half-open range [l, r), use prefix[r] - prefix[l].
- For one-based inclusive ranges, convert endpoints carefully.
在 Block 题里长什么样
答题时通常会看到这些步骤被拆成代码块。
- 1Read N and values.
- 2Create prefix array of size N + 1.
- 3Loop through values to fill prefix.
- 4For each range, subtract prefix endpoints.
- 5Update or print the requested result.
题目里怎么出现
读题时先找这些信号，再决定答案区应该选哪些 blocks。
- The story asks about total over a segment/window/range.
- Many ranges are checked.
- Recomputing each range from scratch would repeat work.
Range sum
一个小型模板，展示代码和 blocks 的对应关系。
C++
vector<int> prefix(N + 1, 0);
for (int i = 0; i < N; i++) {
prefix[i + 1] = prefix[i] + values[i];
}
int sum = prefix[r] - prefix[l];Python
prefix = [0] * (N + 1)
for i in range(N):
prefix[i + 1] = prefix[i] + values[i]
sum_value = prefix[r] - prefix[l]对应 block 顺序
- 1Read values.
- 2Create prefix array.
- 3Fill prefix cumulatively.
- 4Read/query range endpoints.
- 5Subtract prefix endpoints.
- 6Use or output the range total.
相关题目
用题库中的相关题目练习这个知识点。
1 道题