PROBLEM LINK: CodeChef: Practical coding for everyone
Author: Kushagra Kinger
Tester: Kushagra Kinger
Editorialist: Kushagra Kinger
DIFFICULTY:
MEDIUM
PREREQUISITES:
Difference Array , Prefix Sum Array.
PROBLEM:
Given a 2d matrix of size nxm , perform range updates and range sum queries where two cells (r1,c1) and (r2,c2) define a range which contains all cells [i,j] such that r1<=i<=r2 and c1<=j<=c2.
QUICK EXPLANATION:
We will use the concept of one dimensional difference array extended to 2d arrays for range updates and 2d prefix sums for answering queries.
EXPLANATION:
Since queries are asked after all the modifications, thus we perform all the modifications first and then answer the queries. Assume that we have performed all the modifications. Now we have to answer range queries in the 2d-matrix which can be done by making a 2d prefix array of the given matrix.I am not explaining the construction of 2d prefix array and then how it’s used to answer range sum queries here as this concept is available on many places on the internet.
Now , we need to worry about how to perform the modifications efficiently, after that 2d prefix array will answer the queries.
For performing range updates , we will use the concept of 2d differene array.
In 1-d difference array, first we proccess the array as follows:
dif[] is the difference array of a[].
Initially dif is similar to a i.e. dif[i]=a[i] (0<=i<size of array).
Then:
for i= 1 to n-1 //zero indexing
dif[i]=dif[i]-a[i-1];
Now if we have to perform modifications of the form k,l,r which means add k in all elements from l to r then we simply add k to dif[l] and -k to dif[r+1](if l and r are valid i.e. 0<=l<n and 0<=r+1<n). If we are asked to perform m such modifications, we keep on doing this operation on the difference array. Finally when all the modifications are performed we make a prefix sum array of this array and the array obtained is the array which we would have got after performing all modifications on the original array.
In this question we will extend this concept to 2d arrays.
Refer the code for step by step process. Basic concept is that, as in 1d array we add k to the starting index and subtract from the index which touches the boundary of the block to be updated. In 2d array , we have to consider 4 indices.If we have to update from (r1,c1) to (r2,c2) then (r1,c1) is the starting index and (r1,c2+1),(r2+1,c1) and (r1+1,c1+1) are the boundary touching indices.
2d Segment trees is an alternative for solving such a problem but it would be overkill to use it here and the construction time of O(nmlog(n)log(m)) may not pass the time limits of this problem. Thus the concept of 2d difference array must be used to perform modifications in O(1) and then 2d prefix array to perform queries in O(1) time, which yields the total time complexity of O(u+q+n*m).
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll a[1001][1001];
ll b[1001][1001];
int main()
{io
ll ans,k;
int n,m,r1,c1,r2,c2,u,q;
cin>>n>>m>>u>>q;
//b will be used as 2d-difference array
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
b[i][j]=a[i][j];
}
}
// Making of difference array
for(int i=1;i<n;i++)
b[i][0]-=a[i-1][0];
for(int i=1;i<m;i++)
b[0][i]-=a[0][i-1];
for(int i=1;i<n;i++)
{
for(int j=1;j<m;j++)
b[i][j]=b[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
}
// Making modifications
while(u--)
{cin>>k>>r1>>c1>>r2>>c2;
// Three boundary touching indices must be checked for validity before
updation
if(c2+1<m)
b[r1][c2+1]-=k;
if(r2+1<n)
b[r2+1][c1]-=k;
if(r2+1<n&&c2+1<m)
b[r2+1][c2+1]+=k;
b[r1][c1]+=k;
}
//Obtaining Modified Array by performing 2d-prefix array computation on the
2d-difference array
for(int i=1;i<n;i++)
b[i][0]+=b[i-1][0];
for(int i=1;i<m;i++)
b[0][i]+=b[0][i-1];
for(int i=1;i<n;i++)
{
for(int j=1;j<m;j++)
b[i][j]=b[i][j]+b[i-1][j]+b[i][j-1]-b[i-1][j-1];
}
//Making 2d prefix array for answering queries
for(int i=1;i<m;i++)
b[0][i]+=b[0][i-1];
for(int i=1;i<n;i++)
b[i][0]+=b[i-1][0];
for(int i=1;i<n;i++)
{
for(int j=1;j<m;j++)
b[i][j]+=(b[i-1][j]+b[i][j-1]-b[i-1][j-1]);
}
//Answering Queries
while(q--)
{ int r1,c1,r2,c2;
cin>>r1>>c1>>r2>>c2;
ans=b[r2][c2];
if(r1-1>=0)
ans-=b[r1-1][c2];
if(c1-1>=0)
ans-=b[r2][c1-1];
if(r1-1>=0&&c1-1>=0)
ans+=b[r1-1][c1-1];
cout<<ans<<"\n";
}
return 0;}
