二维前缀和和差分
二维前缀和和差分
1.二维前缀和
\[s_{i,j}=s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}
\]
\[s_{x_2,y_2}-s_{x_1-1,y_2}-s_{x_2,y_1-1}+s_{x_1-1,y_1-1}
\]
前缀和推广
例题：有 \(n\) 个数，找出 \(n - 1\) 个数，使得最大公因数最大
解法：枚举 \(n\) 个数，不选一个，找出前缀公约数和后缀公约数，然后再并起来算一次，就可以了
例题：有 \(n\) 个数，找出 \(n - 1\) 个数，使得最大公因数最大
解法：枚举 \(n\) 个数，不选一个，找出前缀公约数和后缀公约数，然后再并起来算一次，就可以了