2d bit is easier to code,
For 1d bit, query(x) return the sum of all the elements which index is <= x, index starting from 1
For 2d bit , query(x,y) return the sum of all the elements of the rectangle (1,1) to (x,y)
Practice Problem:Matsum
/*
*************************
Id : Matrix.code
Task:
Date:
**************************
*/
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define Long long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define forn(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define gc getchar_unlocked
#define PI acos(-1.0)
#define INF 1<<29
#define EPS 1e-9
#define Fr first
#define Sc second
#define Sz size()
#define lc ((n)<<1)
#define rc ((n)<<1|1)
#define db(x) cout << #x << " -> " << x << endl;
#define Di(n) int n;si(n)
#define Dii(a,b) int a,b;si(a);si(b)
#define Diii(a,b,c) int a,b,c;si(a);si(b);si(c)
#define Si(n) si(n)
#define Sii(a,b) si(a);si(b)
#define Siii(a,b,c) si(a);si(b);si(c)
#define min(a,b) ((a)>(b) ? (b) : (a) )
#define max(a,b) ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}
/*************************** END OF TEMPLATE ****************************/
const int N = 2013;
Long bit[N][N];
int a[N][N];
void update(int x,int y,int val)
{
for(int i= x; i< N ; i += i&-i) {
for(int j = y; j < N; j += j&-j) {
bit[i][j] += val;
}
}
}
Long query(int x,int y)
{
Long r = 0;
for(int i = x; i> 0; i-= i&-i ) {
for(int j = y; j > 0; j-= j&-j ) {
r += bit[i][j];
}
}
return r;
}
char s[5];
int main()
{
Di(t);
while(t--){
Di(n);
forn(i,n+1) forn(j,n+1) bit[i][j] = 0 , a[i][j] = 0;
while(scanf("%s",s)) {
if(strcmp(s,"END") == 0 ) break;
if(strcmp(s,"SET") == 0) {
Diii(x,y,u);
x++,y++;
update(x,y,u - a[x][y]);
a[x][y] = u;
}
if(strcmp(s,"SUM") == 0){
Dii(x1,y1);
Dii(x2,y2);
x1 ++ ,y1 ++;
x2 ++, y2 ++;
printf("%lld\n", query(x2,y2) - query(x2,y1-1) - query(x1-1,y2) + query(x1-1,y1-1));
}
}
}
}
Code for Fun 