【算法2-1】前缀和、差分与离散化

荀子曰:不积跬步,无以至千里;不积小流,无以成江海。这句话揭示了世间万物整体和部分之间的关系——庞大的整体由若干个体组成;单个个体虽小,但经过一点一滴的累积,也能聚成一个庞大的整体。学习工作贵在不断积累,不断充实、丰富、完善自己,所有的努力都会有回报。

在算法竞赛中,利用整体和部分的性质可以达成很多目的,例如利用前缀和可以在常数时间 复杂度中查询区间和,利用差分在常数时间复杂度对序列进行区间操作,或者利用离散化去除无用数据区间,通过放缩保留有用的数据。这些操作使得我们不必每次都要重复处理个体的数据,而是直接对整体进行处理,从而降低时间复杂度,提升运算效率。这一章将会学习前缀和、差分和离散化的思想,并使用这些思想完成一些简单的任务。

该题单内容将继续改进。

对应进阶篇第 2 章。


  1. P8218 - 【深进1.例1】求区间和
  2. P1719 - 最大加权矩形
  3. P1314 - [NOIP 2011 提高组] 聪明的质监员
  4. P2367 - 语文成绩
  5. P3397 - 地毯
  6. P1496 - 火烧赤壁
  7. P1955 - [NOI2015] 程序自动分析
  8. P1884 - [USACO12FEB] Overplanting S
  9. P2004 - 领地选择
  10. P3017 - [USACO11MAR] Brownie Slicing G
  11. P3406 - 海底高铁
  12. P1083 - [NOIP 2012 提高组] 借教室
  13. P2882 - [USACO07MAR] Face The Right Way G
  14. P4552 - [Poetize6] IncDec Sequence
  15. P3029 - [USACO11NOV] Cow Lineup S
  16. P1904 - 天际线
  17. P4375 - [USACO18OPEN] Out of Sorts G
  18. P5937 - [CEOI 1999] Parity Game