高維前綴和

一、概述

高維前綴和是一種解決多維度數據求和問題的演算法，可以用於統計圖像、地圖等場景中的像素值、區域和等問題。該演算法首次出現在1986年James Abello和Jeffrey S. Vitter兩人的論文《Random Sampling from Multidimensional Distributions》中。基本思想是將每個維度的前綴和預處理出來，然後通過簡單的計算獲取任意矩形區域的和。

二、二維前綴和

首先，我們從二維前綴和開始介紹，以方便更好地理解高維前綴和。二維前綴和可以用於求解矩陣中某個矩形區域的和。定義矩陣 $M$ 的前綴和 $S$ 為：

S[i][j] = M[1][1] + M[1][2] + ... + M[1][j]
         + M[2][1] + M[2][2] + ... + M[2][j]
         + ...
         + M[i][1] + M[i][2] + ... + M[i][j]

顯然，$S[i][j]$ 表示矩陣 $M$ 左上角到 $(i,j)$ 位置的所有元素之和。

求解任意矩形區域的和時，可以利用前綴和進行快速計算。假設要求解矩形 $(x1,y1)$ 到 $(x2,y2)$ 中所有元素的和，即 $\sum_{i=x1}^{x2}\sum_{j=y1}^{y2}M[i][j]$。通過前綴和，可以得到下面的計算公式：

sum = S[x2][y2] - S[x2][y1-1] - S[x1-1][y2] + S[x1-1][y1-1]

通過該公式，可以用 $O(1)$ 的時間複雜度求解任意矩形區域的和。

三、高維前綴和

對於 $n$ 維的數組而言，可以使用類似二維前綴和的方式進行求解。定義 $n$ 維數組 $A$ 的前綴和為：

S[p1][p2]...[pn] = A[1][1]...[1][p1][1]...[1][p2]...[1][pn]
                  + A[1][1]...[1][p1][1]...[1][p2]...[2][pn]
                  + ...
                  + A[1][1]...[1][p1][2]...[m1][1]...[1][pn]
                  + ...
                  + A[1][n]...[m1][n][p1][1]...[1][p2]...[1][pn]
                  + ...
                  + A[m1][1]...[m1][n][p1][1]...[1][p2]...[1][pn]
                  + ...
                  + A[m1][m2]...[m_n][p1][1]...[1][p2]...[1][pn]

其中，$m_i$ 表示第 $i$ 維的長度，$p_i$ 表示在第 $i$ 維中要求和的最大下標。

類比二維前綴和，對於 $n$ 維數組 $A$，為了快速地計算任意多維矩形區域的和，可以預處理出 $n$ 維前綴和數組 $S$。對於 $n$ 維矩形區域 $R$，可以使用下面的公式進行計算：

sum = S[p1][p2]...[pn] - S[p1][p2]...[q_n-1][pn] - ... - S[p1][q_2-1]...[q_n-1][pn] + S[p1][q_2-1]...[q_n-1][q_n-1]
    - S[q_1-1][p2]...[q_n-1][pn] + S[q_1-1][q_2-1]...[q_n-1][pn] + ... + S[q_1-1][q_2-1]...[q_n-1][q_n-1] 

其中，$p_i$ 表示在第 $i$ 維中要求和的最大下標，$q_i$ 表示在第 $i$ 維中要求和的最小下標。

四、代碼示例

下面是使用 C++ 實現的二維前綴和和高維前綴和的代碼示例。

二維前綴和：

int n, m;
int a[MAX_N][MAX_M];
int s[MAX_N][MAX_M];

void precompute2D() {
    // 計算前綴和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + a[i][j];
        }
    }
}

int query2D(int x1, int y1, int x2, int y2) {
    return s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1];
}

高維前綴和：

const int MAX_D = 10;
const int MAX_SIZE = 1 << MAX_D;
int n, m;
int d[MAX_D]; // 每維的大小
int a[MAX_SIZE][MAX_SIZE][MAX_D];
int s[MAX_SIZE][MAX_SIZE][MAX_D];

void precomputeND() {
    // 計算前綴和
    for (int k = 0; k < MAX_D; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                s[i][j][k] = s[i][j-1][k] + s[i-1][j][k] - s[i-1][j-1][k] + a[i][j][k];
            }
        }
    }
}

int queryND(int *p, int *q) {
    int sum = 0;
    for (int k = 0; k < MAX_D; k++) {
        int p1 = p[k]+1, q1 = q[k];
        for (int i = k+1; i < MAX_D; i++) {
            p1 *= d[i];
            q1 *= d[i];
        }
        int p2 = 1, q2 = 0;
        for (int i = 0; i < k; i++) {
            p2 *= d[i];
            q2 *= d[i];
        }
        sum += s[q1][q2][k] - s[q1][p2-1][k] - s[p1-1][q2][k] + s[p1-1][p2-1][k];    
    }
    return sum;
}