ZeroJudge 解題筆記：d796. 區域調查

作者：王一哲
日期：2026年5月27日


ZeroJudge 題目連結：d796. 區域調查

解題想法

這題理論上可以用線段樹解題，但是程式碼非常長，我只寫了二元索引樹版本，0.3 s 過關，Python 會超時。

Python 程式碼

測資 #0 50%，4.7s，90.3 MB。測資 #1 開始超時。如果把二維串列攤平成一維串列，應該還可以再快一點。

class BIT2D:
    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.arr = [[0]*(m+1) for _ in range(n+1)]
        self.tree = [[0]*(m+1) for _ in range(n+1)]

    def _lowbit(self, x):
        return x & (-x)
    
    def _update(self, x, y, delta):
        i = x
        while i <= self.n:
            j = y
            while j <= self.m:
                self.tree[i][j] += delta
                j += self._lowbit(j)
            i += self._lowbit(i)
    
    def _query(self, x, y):
        total = 0
        i = x
        while i > 0:
            j = y
            while j > 0:
                total += self.tree[i][j]
                j -= self._lowbit(j)
            i -= self._lowbit(i)
        return total

    def update_val(self, x, y, val):
        delta = val - self.arr[x][y]
        self._update(x, y, delta)
        self.arr[x][y] = val

    def query_range(self, x1, y1, x2, y2):
        if x1 > x2: x1, x2 = x2, x1
        if y1 > y2: y1, y2 = y2, y1
        return self._query(x2, y2) - self._query(x1 - 1, y2) - self._query(x2, y1 - 1) + self._query(x1 - 1, y1 - 1)

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        N = int(data[ptr])
        Q = int(data[ptr+1])
        ptr += 2
        bit = BIT2D(N, N)
        for i in range(1, N+1):
            for j in range(1, N+1):
                v = int(data[ptr])
                ptr += 1
                bit.update_val(i, j, v)
        for _ in range(Q):
            op = int(data[ptr])
            ptr += 1
            if op == 1:
                x1 = int(data[ptr])
                y1 = int(data[ptr+1])
                x2 = int(data[ptr+2])
                y2 = int(data[ptr+3])
                ptr += 4
                ans = bit.query_range(x1, y1, x2, y2)
                result.append(f"{ans:d}\n")
            else:
                x = int(data[ptr])
                y = int(data[ptr+1])
                v = int(data[ptr+2])
                ptr += 3
                bit.update_val(x, y, v)
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

二元索引樹，使用時間約為 0.3 s，記憶體約為 4 MB，通過測試。

#include <cstdio>
#include <vector>
#include <algorithm>
typedef long long LL;
using namespace std;

class BIT2D {
private:
    int n, m;
    vector<vector<LL>> arr, tree;
    
    int _lowbit(int x) {
        return x & (-x);
    }

    void _update(int x, int y, int delta) {
        for(int i=x; i<=n; i += _lowbit(i)) {
            for(int j=y; j<=m; j += _lowbit(j)) {
                tree[i][j] += delta;
            }
        }
    }
    
    LL _query(int x, int y) {
        LL total = 0;
        for(int i=x; i>0; i -= _lowbit(i)) {
            for(int j=y; j>0; j -= _lowbit(j)) {
                total += tree[i][j];
            }
        }
        return total;
    }

public:
    BIT2D(int N, int M) {
        n = N;
        m = M;
        arr.assign(n+1, vector<LL> (m+1, 0));
        tree.assign(n+1, vector<LL> (m+1, 0));
    }

    void update_val(int x, int y, LL val) {
        LL delta = val - arr[x][y];
        arr[x][y] = val;
        _update(x, y, delta);
    }

    LL query_range(int x1, int y1, int x2, int y2) {
        if (x1 > x2) swap(x1, x2);
        if (y1 > y2) swap(y1, y2);
        return _query(x2, y2) - _query(x1 - 1, y2) - _query(x2, y1 - 1) + _query(x1 - 1, y1 - 1);
    }

    void printBIT() {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                printf("%lld ", arr[i][j]);
            }
            printf("\n");
        }
    }
};

int main() {
    int N, Q;
    while(scanf("%d %d", &N, &Q) != EOF) {
        BIT2D bit(N, N);
        // 讀取陣列 A 的內容，同時用 bit.update_val 更新數值
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                LL val;
                scanf("%lld", &val);
                bit.update_val(i, j, val);
            }
        }

        for(int q=0; q<Q; q++) {
            int op;
            scanf("%d", &op);
            if (op == 1) {
                int x1, y1, x2, y2;  // 題目是 1-base
                scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
                printf("%lld\n", bit.query_range(x1, y1, x2, y2));
            } else {
                int x, y;
                LL v;
                scanf("%d %d %lld", &x, &y, &v);
                bit.update_val(x, y, v);
            }
        }
    }
    return 0;
}