原點在左下角。

x 方向左而右由 1 ~ N, y 方向下而上由 1 ~ N 的一個方形數字。

請算出每組 （x1, y1）to（x2, y2）的數字合計。

示意圖
3 3 3
2 2 3
1 2 3

v0

一開始就想肯定有公式解

朝著F([x1,y1],[x2,y2])

去思考

後來發現有點難

v1

後來想到F(x,y)去return當下格子數字 但這樣O()會超級大 exF(7,5) => F(3,2) O(20)

v2

後來的想法是F(n) 去算 NxN內的數字和

F(1) = 1

F(2) = F(1) + 2 * (2 * 2 - 1)

F(3) = F(1) + F(2) + 3 * (3*2 -1)

F(n) = F(n-1) + n*(2*n-1)
     =        + 2n^2 - n

再從 F(1),F(n),F(n+1)去推 F(n)公式解 發現可以拆成

F(n) = 2n^2 - n
     = S(2n^2) - S(n)
     = 2(n(n+1)(2n+1)/6) - (n+1)n/2

至此 F(n) 求出來了

之後再推導出F(x,y) 就可以更快了

F(X,Y)

F(x,y) = F(Y) + 6 * 5 + 7 * 5
       =      + (X-Y)XY - (Y(Y+1)(2Y+1)/6)