前缀和
01 / 共享的机制
前置花一次 O(N) 构建累积表 —— 之后的每次区间查询就退化成一次常数级减法。 把这个套路反过来用,就能在区间更新上同样廉价。
在上面选一个子模式。每个子模式都可以单独跳转 —— 从题目最像的那个开始。
↑ 选一个— / 什么时候用哪个
一维线性
当对一个固定数组有很多次区间求和查询时使用。
区间和 · 累计 · LC 303
二维网格
用于矩阵上的矩形查询 —— 四个角上做容斥。
矩形区域 · 块和 · LC 304
差分
反过来用:很多次区间更新,最后一次性扫出每个位置的值。
区间加 · 拼车 · 航班预订
哈希映射
统计和等于目标值的子数组数 —— 前缀和 + 已见前缀的哈希表。
和为 K · 整除 K · LC 560