vector<vector<int>> matrix;
int M = matrix.size(), N = matrix[0].size();
// update > > sum
// update O(1); sum O(n^2)
int M = matrix.size(), N = matrix[0].size();
// update > > sum
// update O(1); sum O(n^2)
[size=13.3333330154419px]set O(1)
[size=13.3333330154419px]sum O(n^2)
void update(int r, int c, int val) {
matrix[r][c] = val;
}
// (r1,c1) upper left, (r2,c2) bottom right
int sum(int r1, int c1, int r2, int c2) {
int res = 0;
for (int i = r1; i <= r2; ++i) {
for (int j = c1; j <= j2; ++j) {
res += matrix[i][j];
}
}
return res;
}
// sum > > update
// dp[i][j] computer sum of rectangle [0,0] --- [0,j] --- [i,0] --- [i,j]
// update O(n^2), sum O(1).
void update(int r, int c, int val) {
matrix[r][c] = val;
}
// (r1,c1) upper left, (r2,c2) bottom right
int sum(int r1, int c1, int r2, int c2) {
int res = 0;
for (int i = r1; i <= r2; ++i) {
for (int j = c1; j <= j2; ++j) {
res += matrix[i][j];
}
}
return res;
}
// sum > > update
// dp[i][j] computer sum of rectangle [0,0] --- [0,j] --- [i,0] --- [i,j]
// update O(n^2), sum O(1).
[size=13.3333330154419px]set O(n^2)
[size=13.3333330154419px]sum O(1)
vector<vector<int>> dp(M,vector(N,0));
void compute() {
dp[0][0] = matrix[0][0];
for (int j = 1; j < N; ++j) {
dp[0][j] = dp[0][j-1] + matrix[0][j];
}
for (int i = 1; i < M; ++i) {
dp[i][0] = dp[i-1][0] + matrix[i][0];
}
for (int i = 1; i < M; ++i) {
for (int j = 1; j < N; ++j) {
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i][j];
}
}
}
void update(int r, int c, int val) {
int dif = val - matrix[i][j];
for (int i = r; i < M; ++i) {
for (int j = c; j < N; ++j) {
dp[i][j] += dif;
}
}
}
int sum(int r1, int c1, int r2, int c2) {
if (r1 == 0 && c1 == 0) return dp[r2][c2];
else if (r1 == 0) return dp[r2][c2] - dp[r2][c1-1];
else if (c1 == 0) return dp[r2][c2] - dp[r1-1][c2];
else return dp[r2][c2] - dp[r1-1][c2] - dp[r2][c1-1] + dp[r1-1][c1-1];
}
// sum ~= update
// update
vector<vector<int>> dp(M,vector(N,0));
void compute() {
dp[0][0] = matrix[0][0];
for (int j = 1; j < N; ++j) {
dp[0][j] = dp[0][j-1] + matrix[0][j];
}
for (int i = 1; i < M; ++i) {
dp[i][0] = dp[i-1][0] + matrix[i][0];
}
for (int i = 1; i < M; ++i) {
for (int j = 1; j < N; ++j) {
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i][j];
}
}
}
void update(int r, int c, int val) {
int dif = val - matrix[i][j];
for (int i = r; i < M; ++i) {
for (int j = c; j < N; ++j) {
dp[i][j] += dif;
}
}
}
int sum(int r1, int c1, int r2, int c2) {
if (r1 == 0 && c1 == 0) return dp[r2][c2];
else if (r1 == 0) return dp[r2][c2] - dp[r2][c1-1];
else if (c1 == 0) return dp[r2][c2] - dp[r1-1][c2];
else return dp[r2][c2] - dp[r1-1][c2] - dp[r2][c1-1] + dp[r1-1][c1-1];
}
// sum ~= update
// update
[size=13.3333330154419px]set O(n)
[size=13.3333330154419px]sum O(n)
vector<vector<int>> dp(M,vector(N,0));
// row dp; dp[i][j] = sum_i_{k = 0}^{k = j};
void compute() {
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (j == 0) dp[i][j] = matrix[i][j];
else dp[i][j] = dp[i][j-1] + matrix[i][j];
}
}
}
void update(int r, int c, int val) {
int dif = val - matrix[i][j];
for (int j = c; j < N; ++j) {
dp[r][j] += dif;
}
}
int sum(int r1, int c1, int r2, int c2) {
int res = 0;
for (int i = r1; i <= r2; ++i) {
res += c1 == 0 ? dp[i][c2] : dp[i][c2] - dp[i][c2-1];
}
return res;
}
vector<vector<int>> dp(M,vector(N,0));
// row dp; dp[i][j] = sum_i_{k = 0}^{k = j};
void compute() {
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (j == 0) dp[i][j] = matrix[i][j];
else dp[i][j] = dp[i][j-1] + matrix[i][j];
}
}
}
void update(int r, int c, int val) {
int dif = val - matrix[i][j];
for (int j = c; j < N; ++j) {
dp[r][j] += dif;
}
}
int sum(int r1, int c1, int r2, int c2) {
int res = 0;
for (int i = r1; i <= r2; ++i) {
res += c1 == 0 ? dp[i][c2] : dp[i][c2] - dp[i][c2-1];
}
return res;
}
[size=13.3333330154419px]set O(log n)
[size=13.3333330154419px]sum O(log n)
Solution:
Lets take an example:
Given a matrix M[R][C], initially set to 0.
We have 2 operations:
1. set r,c,Value element to value.
2.range sum r1,c1,r2,c2 ; return the sum of all the elements r,c such that r1<=r<=r2, c1<=c<=c2;
This can be done using Fenwick 2D Point updation Tree.
1. Use update(r,c,Value) for 1st operation;
void update(int x , int y , int val){
int y1;
while (x <= max_x){
y1 = y;
while (y1 <= max_y){
tree[x][y1] += val;
y1 += (y1 & -y1);
}
x += (x & -x);
}
}
2. read(r1,c1,r2,c2) = read(r2,c2) - read(r2,c1-1) - read(r1-1,c2) + read(r1-1,c1-1);
int read(int x,int y){ // return sum from 1,1 to x,y.
int sum= 0;
while( x){
int y1 = y;
while(y1){
sum += tree[x][y1];
y1 -= y1 & -y1;
}
x -= x & -x;
}
return sum;
}
import java.lang.*;
public class BIT2DSumAndUpdate {
// Given an NxN matrix of positive and negative integers, write code to find the
// range sum and update matrix
// Approach#1 sum: O(n^2) time, update:O(1) time.
static int sum(int[][] matrix, int r1, int c1, int r2, int c2) {
int sum = 0;
for (int r = r1; r <= r2; ++r) {
for (int c = c1; c <= c2; ++c) {
sum += matrix[r][c];
}
}
return sum;
}
static void update (int[][] matrix, int r1, int c1, int val){
matrix[r1][c1] = val;
}
// Approach#2 sum: O(1) time, update:O(n^2) time.
static int[][] processMatrix(int[][] m) {
if (m == null) return null;
int[][] sumMatrix = new int[m.length][m[0].length];
sumMatrix[0][0] = m[0][0];
for (int j = 1; j < m[0].length;j++){
sumMatrix[0][j]=sumMatrix[0][j-1]+m[0][j];
//System.out.println(0+","+j+" - "+sumMatrix[0][j]+",");
}
for (int i = 1; i < m.length;i++){
sumMatrix[i][0]=sumMatrix[i-1][0]+m[i][0];
//System.out.println(i+","+0+" - "+sumMatrix[i][0]+",");
}
for (int i =1; i< m.length;i++) {
for (int j=1; j < m[0].length;j++){
sumMatrix[i][j] = sumMatrix[i-1][j]+sumMatrix[i][j-1]-sumMatrix[i-1][j-1]+m[i][j];
//System.out.println(i+","+j+" - "+sumMatrix[i][j]+",");
}
}
return sumMatrix;
}
static int sum2(int[][] sumMatrix, int r1, int c1, int r2, int c2) {
if (r1 == 0 && c1 == 0){
return sumMatrix[r2][c2];
}
else if (r1 == 0){
return sumMatrix[r2][c2]-sumMatrix[r2][c2-1];
}
else if (c1 == 0 ){
return sumMatrix[r2][c2]-sumMatrix[r1-1][c2];
} else {
return sumMatrix[r2][c2]-sumMatrix[r2][c1-1]-sumMatrix[r1-1][c2]+sumMatrix[r1-1][c1-1];
}
}
static void update2(int[][] matrix, int[][] sumMatrix,int r1, int c1, int val){
int diff= val - matrix[r1][c1];
for (int i = r1; i < sumMatrix.length;i++){
for (int j = c1; j< sumMatrix[0].length; j++){
sumMatrix[i][j]+=diff;
}
}
}
// Approach#3 sum: O(log n) time, update:O(log n) time.
static int[][] processMatrixTree(int[][] m) {
if (m == null) return null;
int[][] tree = new int[m.length+1][m[0].length+1];
for( int i = 1; i <= m.length;i++){
for(int j = 1; j <=m[0].length;j++){
//System.out.println(i+","+j+". sumFirst="+tree[i][j]);
updateBuilde3(tree, i, j, m[i-1][j-1]);
}
}
return tree;
}
static int sum3(int[][] tree, int r1, int c1, int r2, int c2) {
if (r1 == 0 && c1 == 0){
return getSum(tree,r2,c2);
}
else if (r1 == 0){
return getSum(tree,r2,c2)-getSum(tree,r2,c2-1);
}
else if (c1 == 0 ){
return getSum(tree,r2,c2)-getSum(tree,r1-1, c2);
} else {
return getSum(tree,r2,c2)-getSum(tree,r2,c1-1)-getSum(tree,r1-1, c2)+getSum(tree,r1-1,c1-1);
}
}
static int getSum(int[][] tree, int i, int j){
int sum = 0;
//System.out.println(i+","+j+". sumAdd="+sum);
i = i+1;
j = j+1;
int j1;
while(i > 0) {
j1 = j;
while(j1 > 0){
sum += tree[i][j1];
///System.out.println(i+","+j1+". sumAdd="+sum);
j1 -= j1 & -j1;
}
i -= i & -i;
}
return sum;
}
static void updateBuilde3(int[][] tree, int i, int j, int val){
//int diff= val - matrix[r1][c1];
int j1;
while(i < tree.length){
j1 = j;
while(j1 < tree[0].length){
tree[i][j1] += val;
//System.out.println(i+","+j1+". sumAfter="+tree[i][j1]);
j1 += (j1 & -j1);
}
i += (i & -i);
}
}
static void update3(int[][] matrix, int[][] tree, int i, int j, int val){
int diff= val - matrix[i][j];
int j1;
while(i < tree.length){
j1 = j;
while(j1 < tree[0].length){
tree[i][j1] += diff;
//System.out.println(i+","+j1+". sumAfter="+tree[i][j1]);
j1 += (j1 & -j1);
}
i += (i & -i);
}
}
//--------------------------------------
public static void main(String[]args) {
int[][] m = {
{1,-2,3,1},
{1,5,-4,1},
{1,1,0,2},
{-1,1,1,-8}};
int[][] m2 = {
{1,-2,3,1},
{1,5,-4,1},
{1,1,0,2},
{-1,1,1,-8}};
int[][] m3 = {
{1,-2,3,1},
{1,5,-4,1},
{1,1,0,2},
{-1,1,1,-8}};
long start = System.nanoTime();
int sum1_1 = sum(m,0,0,2,3);
long end = System.nanoTime();
update(m, 2,3,3);// 2->3
int sum1_2 = sum(m,0,0,2,3);
System.out.println("Time:"+(long)(end-start)+",sum=" +sum1_1+",sum2=" +sum1_2);
int[][] sumMatrix = processMatrix(m2);
long start2 = System.nanoTime();
int sum2_1 = sum2(sumMatrix,0,0,2,3);
long end2 = System.nanoTime();
update2(m2, sumMatrix, 2,3,3);// 2->3
int sum2_2 = sum2(sumMatrix,0,0,2,3);
System.out.println("Time:"+(long)(end2-start2)+",sum=" +sum2_1+",sum2=" +sum2_2);
int[][] tree = processMatrixTree(m3);
long start3 = System.nanoTime();
int sum3_1 = sum3(tree,0,0,2,3);
long end3 = System.nanoTime();
update3(m3, tree, 2,3,3);// 2->3
int sum3_2 = sum3(tree,0,0,2,3);
System.out.println("Time:"+(long)(end3-start3)+",sum=" +sum3_1+",sum2=" +sum3_2);
}
}
No comments:
Post a Comment