POJ 1195 Mobile Phones：二維樹狀數組 (2D BIT) 完整解析與實現

題目概述

POJ 1195 Mobile Phones 是一道經典的二維樹狀數組（2D Binary Indexed Tree，2D BIT）應用題。題目給定一個 S × S 的正方形區域，支援三種操作：

• 操作 0：初始化，輸入 S，建立大小為 (S+1) × (S+1) 的 BIT。
• 操作 1：單點更新，輸入 x, y, a，將座標 (x, y) 的值增加 a。
• 操作 2：區間查詢，輸入 l, b, r, t，查詢以 (l, b) 為左上角、(r, t) 為右下角的矩形區域內所有元素之和。
• 操作 3：結束當前測試案例。

由於座標從 0 開始，實作時需將座標 +1 轉為 1-based 索引。

核心算法：二維樹狀數組

二維 BIT 將一維 BIT 的思想推廣到二維平面。定義 c[x][y] 為以 (x, y) 為右下角、寬高分別為 lowbit(x)、lowbit(y) 的矩形區域和。

關鍵操作

// lowbit 取最低位 1
int lowbit(int x) { return x & (-x); }

// 單點更新：在 (x, y) 加上 value
void add(int x, int y, int value) {
    int i = y;
    while (x <= n) {
        y = i;
        while (y <= n) {
            c[x][y] += value;
            y += lowbit(y);
        }
        x += lowbit(x);
    }
}

// 前綴和查詢：求 (1,1) 到 (x,y) 的矩形和
int get_sum(int x, int y) {
    int sum = 0, i = y;
    while (x > 0) {
        y = i;
        while (y > 0) {
            sum += c[x][y];
            y -= lowbit(y);
        }
        x -= lowbit(x);
    }
    return sum;
}

// 區間查詢：利用容斥原理
int query_rect(int l, int b, int r, int t) {
    return get_sum(r, t) - get_sum(l-1, t) - get_sum(r, b-1) + get_sum(l-1, b-1);
}

完整 C++ 實現

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 1000 + 35;
int n;
int c[MAXN][MAXN];

void clear() { memset(c, 0, sizeof(c)); }
int lowbit(int x) { return x & (-x); }

void add(int x, int y, int value) {
    int i = y;
    while (x <= n) {
        y = i;
        while (y <= n) {
            c[x][y] += value;
            y += lowbit(y);
        }
        x += lowbit(x);
    }
}

int get_sum(int x, int y) {
    int sum = 0, i = y;
    while (x > 0) {
        y = i;
        while (y > 0) {
            sum += c[x][y];
            y -= lowbit(y);
        }
        x -= lowbit(x);
    }
    return sum;
}

int main() {
    int op;
    while (scanf("%d", &op) == 1) {
        if (op == 0) {
            scanf("%d", &n);
            n++;  // 座標從 0 開始，轉為 1-based
            clear();
        } else if (op == 1) {
            int x, y, a;
            scanf("%d %d %d", &x, &y, &a);
            add(++x, ++y, a);
        } else if (op == 2) {
            int l, b, r, t;
            scanf("%d %d %d %d", &l, &b, &r, &t);
            l++; b++; r++; t++;
            int ans = get_sum(r, t) - get_sum(l-1, t) - get_sum(r, b-1) + get_sum(l-1, b-1);
            printf("%d\n", ans);
        } else break;
    }
    return 0;
}

複雜度分析

• 時間複雜度：單次更新或查詢為 O(log² S)，對於 S ≤ 1000 極其高效。
• 空間複雜度：O(S²)，約 4MB，符合限制。

常見坑點提醒

1. 座標轉換：輸入座標從 0 開始，BIT 內部使用 1-based，必須 ++x, ++y。
2. 多測試案例：每次 op==0 重新初始化 n 並清空數組。
3. 區間查詢邊界：使用容斥原理時注意 l-1、b-1 不會小於 0（因已 +1）。

二維樹狀數組是處理動態二維區間和的利器，掌握其模板可輕鬆解決同類問題。