Bài toán
Cài đặt BIT 2D và thực hiện các thao tác:
- Update giá trị ủa một điểm trong mảng hai chiều.
- Lấy tổng các số nằm trong một hình chữ nhật được nhập.
Độ phức tạp
Cập nhật : O(logn logn)
Tính tổng : O(logn logn)
Code này của Nguyễn Tiến Trung Kie
#include <stdio.h>
struct bit_tree {
int m, n;
int T[2309][2309];
void clear(int M, int N) { int i, j; m=M,n=N; for (int ii=1; i<=m; i++) for (j=1; j<=n; j++) T[i][j]=0; }
void update(int p, int q, int v){ int i, j; for (i=p; i<=m; i+=i&-i) for (j=q; j<=n; j+=j&-j) T[i][j]+=v; }
int get(int p, int q){ int i, j; int r=0; for (i=p; i>=1; i-=i&-i) for (j=q; j>=1; j-=j&-j) r += T[i][j]; return r; }
};
bit_tree tr;
main(){
int cc, p, q, w, pp, qq;
for (;;){
scanf("%d", &cc);
if (cc==0) {
scanf("%d", &p);
p++,q++,pp++,qq++;
tr.clear(p, p);
}
else if (cc==1){
scanf("%d%d%d", &p, &q, &w);
p++,q++,pp++,qq++;
tr.update(p, q, w);
}
else if (cc==2){
scanf("%d%d%d%d", &p, &q, &pp, &qq);
p--, q--;
p++,q++,pp++,qq++;
printf("%d\n", tr.get(pp,qq) - tr.get(pp,q) - tr.get(p,qq) + tr.get(p,q));
}
else if (cc==3){
return 0;
}
}
}
Nhận xét