d796 - 區域調查
題目描述
題目給定一個 N x N 的矩陣，並有 Q 個操作。操作分為兩種：
- 查詢：給定矩陣的一個子矩形 (x1, y1) 到 (x2, y2)，求該子矩形中所有元素的總和。
- 更新：給定矩陣中的一個元素 (x1, y1)，將其值修改為 V。
解題思路
這題可以使用二維 Binary Indexed Tree (BIT) 來解決。BIT 是一種高效的資料結構，可以用於進行區間查詢和單點更新。
首先，我們初始化一個 N x N 的 BIT 陣列，並將原始矩陣中的元素值加到 BIT 中。 對於查詢操作，我們可以使用 BIT 的特性，通過四次查詢計算出子矩形的總和。具體來說，我們計算 (x2, y2) 的前綴和，然後減去 (x1-1, y2)、(x2, y1-1) 和 (x1-1, y1-1) 的前綴和，即可得到子矩形的總和。 對於更新操作，我們只需要將新的值與原始值之間的差值加到 BIT 中即可。
複雜度分析
- 時間複雜度: O(Q * log^2(N))，其中 Q 是操作的數量，N 是矩陣的大小。每次查詢和更新操作都需要 O(log^2(N)) 的時間。
- 空間複雜度: O(N^2)，用於儲存 BIT 陣列。
程式碼
#include <iostream>
using namespace std;
int n,q,is,x1,y1,x2,y2,va;
int a[251][251],BIT[251][251];
int lowerbit(int x){
return x&(-x);
}
int update(int x,int y,int v){
for(int i=x;i<=n;i+=lowerbit(i))
for(int j=y;j<=n;j+=lowerbit(j))
BIT[i][j]+=v;
}
int sum(int x,int y){
int rt=0;
for(int i=x;i>0;i-=lowerbit(i))
for(int j=y;j>0;j-=lowerbit(j))
rt+=BIT[i][j];
return rt;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> q;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
cin >> a[i][j];
update(i,j,a[i][j]);
}
while(q--){
cin >> is;
if(is==1){
cin >> x1 >> y1 >> x2 >> y2;
int tmpx=max(x1,x2),tmpy=max(y1,y2);
x1=min(x1,x2);
y1=min(y1,y2);
x2=tmpx;
y2=tmpy;
cout << sum(x2,y2) - sum(x1-1,y2) - sum(x2,y1-1) + sum(x1-1,y1-1) << "\n";
}
else{
cin >> x1 >> y1 >> va;
update(x1,y1,va-a[x1][y1]);
a[x1][y1]=va;
}
}
}