0オリジンで考えた場合の絵
シグマの順序交換
$\sum_{i=0}^{N-2}\sum_{j=i+1}^{N-1} f(A_i, A_j) = \sum_{j=1}^{N-1}\sum_{i=0}^{j-1} f(A_i, A_j)$
$0 \leq i < j < N$ を見て、「$i$ を固定→ $j$ を動かす」と「$j$ を固定→ $i$ を動かす」を考えるとわかりやすい。
$f(x, y) = f(y, x)$ ($f$ が可換) の場合
- $(A_i)_i$ の順番を入れ替えて良い
- 例えばソートしてもよい
- (正方形-対角線)/2 という計算ができる
$(N-1) \sum_{i=0}^{N-1} A_i$ みたいな $\mathrm{O}(N^2 \max A_i)$ くらいの値の計算をすると64bit符号付き整数（最大 $9.2\times10^{18}$ くらい）でオーバーフローが発生することがある
- 例えば $N\leq 10^5, A_i \leq 10^9$ みたいな場合、総和は $10^{19}$ くらいになってしまう。
- $N \leq 3\times 10^5, A_i \leq 10^8$ みたいな場合であれば、総和は $9\times 10^{18}$ になってぎりぎり大丈夫
線形性
- 大事