整体和部分的性质至关重要。
通常辅助其余算法。
前缀和与二维前缀和
整体可分为若干部分。
B3612 求区间和
模板。
P1719 最大加权矩形
枚举左右边界,用每行的区间和跑最大子段和。
P1314 「NOIP2011TG」聪明的质检员
二分,每次预处理数量与价值的前缀和,然后枚举区间计算。
差分
变化量,部分经过一系列变化可变为整体。
P2367 语文成绩
模板。
P3397 地毯
令一个位置的变化量能影响到以其为左上角到全局右下角的矩形,用前缀和的方式即可实现修改和累加。