算法笔记的第一篇文章
前缀和:
在做题时,我们经常会遇见这种问题:
给你一个长度为 \(n\) 的序列 \(a\),有 \(q\) 次询问,每次给出一个区间 \(\left[L, R\right]\), 请输出 \(a_l+a_{l + 1}+\cdots+a_r\) 的和。
对于这种问题,最为简单的方式莫过于 \(\operatorname{O}(nq)\) 暴力了。
但有没有更快的方法呢?
由于加法是可逆的,所以我们可以把区间 \(\left[L, R\right]\) 拆分成区间 \(\left[1, R\right]\) 减去区间 \(\left[1, L-1\right]\),所以我们可以预处理 \(a\) 的每一个前缀,达到 \(\operatorname{O}(1)\) 的查询。
预处理公式:
\[s_i =s_{i-1}+a_i \]差分:
给你一个长度为 \(n\) 的序列 \(a\),有 \(q\) 次操作,每次给出一个区间 \(\left[L, R\right]\), 表示将 \(\left[L, R\right]\) 中的每一个数加 1, 让你输出 \(q\) 次操作后的数列。
对于这个问题,我们肯定能够想到 \(\operatorname{O}(nq)\) 的暴力写法。但可以用差分优化到 \(\operatorname{O}(n+q)\) 。
根据上述前缀和的公式我们不难发现,如果我们把 \(a_i\) 增加 1,那么 \(s_i,s_{i+1}\cdots s_n\) 都会增加 1。设差分数组为 \(d\), 那么我们把 \(d_L\) 加 1,把 \(d_R\) 减 1 即可。
但因为 \(\sum\limits_{j=1}^id_j\) 要等于 \(a_i\),根据前缀和公式,我们可以逆向求得 \(d_i= a_i-a_i-1\) 然后在 \(d\) 数组上操作就可以了。
标签:right,前缀,差分,一维,区间,operatorname,left From: https://www.cnblogs.com/caoshurui/p/18042027