Mobiles from IOI 2001

mobiles.cpp

#include <iostream>

using namespace std;

/* MAXN needs to be a power of 2. */
#define MAXN (1 << 10)

/* A should be initialized to zeroes. */
int A[MAXN][MAXN];

/* Logically executes array[x][y] += v. */
void bit_add(int x, int y, int v) {
  for(int i = x | MAXN; i < (MAXN << 1); i += i & -i) {
    for(int j = y | MAXN; j < (MAXN << 1); j += j & -j) {
      A[i ^ MAXN][j ^ MAXN] += v;
    }
  }
}

/* Returns the sum of array[i][j] for 0 <= i <= x and 0 <= j <= y. */
int bit_get(int x, int y) {
  int ret = 0;
  for(int i = x; ; i &= i - 1) {
    for(int j = y; ; j &= j - 1) {
      ret += A[i][j];
      if(!j) break;
    }
    if(!i) break;
  }
  return ret;
}

int main() {
  int cmd;
  cin >> cmd >> cmd;
  for(cin >> cmd; cmd != 3; cin >> cmd) {
    if(cmd == 1) {
      int x, y, v;
      cin >> x >> y >> v;
      bit_add(x, y, v);
    } else {
      int xlo, ylo, xhi, yhi;
      cin >> xlo >> ylo >> xhi >> yhi;

      int res = bit_get(xhi, yhi);
      if(xlo) res -= bit_get(xlo - 1, yhi);
      if(ylo) res -= bit_get(xhi, ylo - 1);
      if(xlo && ylo) res += bit_get(xlo - 1, ylo - 1);
      cout << res << '\n';
    }
  }
  return 0;
}