ACM竞赛实践：1_复杂度分析

主要是对复杂度进行分析，想到合适的解法。

3.10前缀和与差分

程序设计中的数学

$$\begin{aligned} 一维前缀和:S_k &= \sum_{i = 1}^k{a_i};\\ \sum_{i = l}^{r}{a_i} &= S_{r}-S_{l-1}\\ \\ 二维前缀和:S_{x,y} &= \sum_{i = 1}^x \sum_{j = 1}^y a_{i,j} = a_{i,j}+S_{i-1,j}+S_{i,j-1}-S_{i-1,j-1}; \\ \sum_{i = x_1}^{x_2} \sum_{j = y_1}^{y_2} {a_{i,j}} &= S_{x_2,y_2}-S_{x_1-1,y_2}-S_{x_2,y_1-1}+S_{x_1-1,y_1-1} \\ \\ 一维差分：D_i &= a_i-a_{i-1};\\ a[l,r] += c 可以转变为 D[l] &+= c, D[r+1] -=c ;\\ a_k &= \sum_{i = 1}^k{D_i}\\ \\ 二维差分：D_{i,j} &= a_{i,j}-a_{i-1,j}-a_{i,j-1}+a_{i-1,j-1};\\ D[x_1][y_1] &+= c;\\ D[x_1][y_2+1] &-= c;\\ D[x_2+1][y_1] &-= c;\\ D[x_2+1][y_2+1] &+= c;\\ \end{aligned} $$