Mobile Phones
Problem Statement Summary Maintain an S S grid (initially all zeros, S 1024) under two operations: Update(x, y, v): add v to cell (x, y). Query(x_1, y_1, x_2, y_2): return the sum of all cells in the rectangle [x_1, x...
Problem Statement
No standalone statement file is available for this entry.
A separate statement file is not available for this entry, so the page focuses on the editorial and implementation.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Problem Statement Summary
Maintain an $S \times S$ grid (initially all zeros, $S \le 1024$) under two operations:
$\textsc{Update}(x, y, v)$: add $v$ to cell $(x, y)$.
$\textsc{Query}(x_1, y_1, x_2, y_2)$: return the sum of all cells in the rectangle $[x_1, x_2] \times [y_1, y_2]$.
Solution: 2D Binary Indexed Tree
A 2D BIT (Fenwick tree) extends the classical 1D structure to support point updates and prefix-sum queries in two dimensions.
Update.
To add $v$ to position $(x, y)$ (1-indexed):
for (int i = x; i <= S; i += i & (-i))
for (int j = y; j <= S; j += j & (-j))
tree[i][j] += v;Prefix sum.
$\displaystyle\mathrm{sum}(x, y) = \sum_{i=1}^{x}\sum_{j=1}^{y} a[i][j]$ is computed by:
int s = 0;
for (int i = x; i > 0; i -= i & (-i))
for (int j = y; j > 0; j -= j & (-j))
s += tree[i][j];Rectangle sum.
By inclusion--exclusion: \[ \mathrm{RectSum}(x_1,y_1,x_2,y_2) = \mathrm{sum}(x_2,y_2) - \mathrm{sum}(x_1{-}1,y_2) - \mathrm{sum}(x_2,y_1{-}1) + \mathrm{sum}(x_1{-}1,y_1{-}1). \]
C++ Implementation
#include <bits/stdc++.h>
using namespace std;
int S;
int tree[1025][1025];
void update(int x, int y, int v) {
for (int i = x; i <= S; i += i & (-i))
for (int j = y; j <= S; j += j & (-j))
tree[i][j] += v;
}
int query(int x, int y) {
int s = 0;
for (int i = x; i > 0; i -= i & (-i))
for (int j = y; j > 0; j -= j & (-j))
s += tree[i][j];
return s;
}
int rectQuery(int x1, int y1, int x2, int y2) {
return query(x2, y2)
- query(x1 - 1, y2)
- query(x2, y1 - 1)
+ query(x1 - 1, y1 - 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int op;
cin >> op >> S; // op == 0: initialise
memset(tree, 0, sizeof(tree));
while (cin >> op) {
if (op == 3) break; // terminate
if (op == 1) {
int x, y, v;
cin >> x >> y >> v;
x++; y++; // convert 0-indexed input to 1-indexed BIT
update(x, y, v);
} else if (op == 2) {
int l, b, r, t;
cin >> l >> b >> r >> t;
l++; b++; r++; t++; // convert to 1-indexed
cout << rectQuery(l, b, r, t) << "\n";
}
}
return 0;
}Complexity Analysis
Update: $O(\log^2 S)$.
Query: $O(\log^2 S)$ (four prefix-sum queries).
Space: $O(S^2) = O(1024^2) \approx 10^6$.
Total time: $O(Q \log^2 S)$ for $Q$ operations.
Code
C++ solution used for this page.
// IOI 2001 - Mobile Phones
// 2D grid with point updates and rectangle sum queries.
// Uses a 2D Binary Indexed Tree (Fenwick Tree).
// Operations: 0=init, 1=update(x,y,v), 2=query(l,b,r,t), 3=terminate.
// Input coordinates are 0-indexed; internally we use 1-indexed BIT.
// Complexity: O(log^2 S) per operation, O(S^2) space.
#include <bits/stdc++.h>
using namespace std;
int S;
int tree[1025][1025];
void update(int x, int y, int v) {
for (int i = x; i <= S; i += i & (-i))
for (int j = y; j <= S; j += j & (-j))
tree[i][j] += v;
}
int query(int x, int y) {
int s = 0;
for (int i = x; i > 0; i -= i & (-i))
for (int j = y; j > 0; j -= j & (-j))
s += tree[i][j];
return s;
}
int rectQuery(int x1, int y1, int x2, int y2) {
return query(x2, y2)
- query(x1 - 1, y2)
- query(x2, y1 - 1)
+ query(x1 - 1, y1 - 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int op;
cin >> op; // op == 0: init
cin >> S;
memset(tree, 0, sizeof(tree));
while (cin >> op) {
if (op == 3) break; // terminate
if (op == 1) {
int x, y, v;
cin >> x >> y >> v;
x++; y++; // convert to 1-indexed
update(x, y, v);
} else if (op == 2) {
int l, b, r, t;
cin >> l >> b >> r >> t;
l++; b++; r++; t++; // convert to 1-indexed
cout << rectQuery(l, b, r, t) << "\n";
}
}
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.