用二維線段樹優化你的查詢演算法

一、什麼是二維線段樹

線段樹是一種數據結構，它可以對一維的區間進行查詢和修改操作。一維線段樹本質上就是一棵二叉樹，每個節點代表一個區間。而二維線段樹則通過拆分成若干個一維線段樹解決二維區間的查詢問題。

在二維平面上建立一棵平衡二叉樹，節點數為 $O(n\log n)$，並且使每個節點代表的區域是相等的。每個節點存儲這個區域的信息。每個節點代表一個矩形，在其兒子節點中將該矩形分成四個區域。具體實現時，只需要在每個節點記錄它的兒子節點的編號即可。

const int MAXN = 1e3;

struct node {
    int data;
    int l, r, d, u; // 左邊界，右邊界，下邊界，上邊界
    int son[4];
} tree[MAXN*MAXN];
int root = 1, tot = 1;

// 區間查詢
int query(int p, int l, int r, int d, int u) {
    if(p == 0) return 0;
    if(l <= tree[p].l && tree[p].r <= r && d <= tree[p].d && tree[p].u <= u) return tree[p].data;
    int res = 0;
    int midx = (tree[p].l+tree[p].r)/2, midy = (tree[p].d+tree[p].u)/2;
    if(l <= midx && d  midx && d <= midy) res += query(tree[p].son[1], l, r, d, u);
    if(l  midy) res += query(tree[p].son[2], l, r, d, u);
    if(r > midx && u > midy) res += query(tree[p].son[3], l, r, d, u);
    return res;
}

二、二維線段樹在常見問題中的應用

二維線段樹的常見用途有區間查詢和矩陣求和。在一個 $N\times M$ 的矩陣中，選擇若干個位置的數，並將它們全部加起來，問題可以轉化為查詢某些行和列的區間和。使用二維線段樹可以將時間複雜度從 $O(NM)$ 優化到 $O((N+Q)\log^2N)$，其中 $Q$ 為查詢次數。

三、使用二維線段樹進行優化

在二維線段樹中，每個節點代表一塊區間，節點內存儲了這一塊區間內的數據。對於第一維的數據，我們可以直接將其放在第一維的線段樹上。而對於第二維的數據，我們可以開一個另外的數組來存儲。在查詢、修改時，二者都會同時被更新。

比如在一個二維平面上，給定點 $(x_1,y_1)$ 和 $(x_2,y_2)$，查詢這兩個點構成的矩形中所有點的權值和。我們可以維護兩棵線段樹，分別對第一維和第二維進行建樹。查詢操作時，時間複雜度為 $O(\log^2n)$。

const int MAXN = 1e3;

struct node {
    int data;
    int l, r, son[2];
} tr[MAXN*4][MAXN*4];
int n;

void buildy(int x, int p, int l, int r) {
    if(l == r) {
        // 對於每個葉子節點，開一個數組儲存值
        for(int i = 1; i <= n; i++) {
            tr[x][p].data += val[i][l];
        }
        return;
    }
    int m = (l+r)/2;
    tr[x][p].l = l, tr[x][p].r = r;
    buildy(x, p*2, l, m);
    buildy(x, p*2+1, m+1, r);
    tr[x][p].data = tr[x][p*2].data+tr[x][p*2+1].data;
}

void buildx(int p, int l, int r) {
    if(l == r) {
        buildy(p, 1, 1, n);
        return;
    }
    int m = (l+r)/2;
    tr[p][0].l = l, tr[p][0].r = r;
    buildx(p*2, l, m);
    buildx(p*2+1, m+1, r);
    for(int i = 1; i <= 4*n; i++) {
        tr[p][i].r = tr[p][0].r;
        tr[p][i].l = tr[p][0].l;
    }
    for(int i = 0; i < n; i++) {
        for(int j = 1; j data+tr[p][i*4+j].son[1]->data;
        }
    }
}

int queryy(int x, int p, int l, int r, int d, int u) {
    if(d <= tr[x][p].l && tr[x][p].r <= u) {
        return tr[x][p].data;
    }
    int m = (tr[x][p].l+tr[x][p].r)/2, res = 0;
    if(d  m) res += queryy(x, p*2+1, l, r, d, u);
    return res;
}

int queryx(int p, int l, int r, int d, int u, int dl, int ur) {
    if(dl <= l && r <= ur) {
        return queryy(p, 1, dl, ur, d, u);
    }
    int m = (l+r)/2, res = 0;
    if(dl  m) res += queryx(p*2+1, m+1, r, d, u, dl, ur);
    return res;
}

四、小結

二維線段樹的常見應用有區間查詢和矩陣求和。它將單維線段樹的思想擴展至二維，拆分成多個一維線段樹，從而可以優化查詢的時間複雜度，減少不必要的計算。在實際應用中，可以將第一維和第二維分別使用不同的數據結構，來達到更好的效果。