前缀和
什么是前缀和：简单来说，有一个 \(x\) 数组和 \(y\) 数组，\(y\) 是 \(x\) 的前缀和数组。
\(y_1=x_1\)
\(y_2=x_1+x_2\)
\(y_3=x_1+x_2+x_3\)
\(y_n=x_1+x_2+x_3+……+x_n\)
求区间和
求前缀和的公式
r[i]=r[i-1]+s[i]
\(r\) 为前缀和数组，要求 \(x\) 到 \(y\) 的区间和的话，那么套上这个公式。
求区间和的公式
r[y]-r[x-1]
二维前缀和公式
r[i][j]=r[i-1][j]+r[i][j-1]-r[i-1][j-1]+a[i][j]