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

荀子曰：不积跬步，无以至千里；不积小流，无以成江海。这句话揭示了世间万物整体和部 分之间的关系——庞大的整体由若干个体组成；单个个体虽小，但经过一点一滴的累积，也能聚 成一个庞大的整体。学习工作贵在不断积累，不断充实、丰富、完善自己，所有的努力都会有回 报。 在算法竞赛中，利用整体和部分的性质可以达成很多目的，例如利用前缀和可以在常数时间 复杂度中查询区间和，利用差分在常数时间复杂度对序列进行区间操作，或者利用离散化去除无 用数据区间，通过放缩保留有用的数据。这些操作使得我们不必每次都要重复处理个体的数据， 而是直接对整体进行处理，从而降低时间复杂度，提升运算效率。这一章将会学习前缀和、差分 和离散化的思想，并使用这些思想完成一些简单的任务。 该题单内容将继续改进。 对应进阶篇第 2 章。