Suppose you want to solve a problem in which you have 3 types of queries in a grid of size $N \times N$: ↵
<br>1. Insert a $1$ in the grid at any position↵
<br>2. Remove a $1$ from any position in the grid↵
<br>3. Count the number of $1$ in a subgrid (ie. any rectangle inside the grid).↵
<br>Initially the grid is empty and there are $Q$ queries. ↵
↵
This can be solved easily by using a 2D BIT. But the conventional 2D BIT has space complexity $O(N^2)$. So if $N <= 10^5$, this won't work. Hence a compressed version of 2D BIT is required. This problem can be solved with an Implicit Treap along with BIT, but the implementation would be too complex. Here is an easy way to solve such a problem.↵
↵
In this implementation an Order Statistics Tree ([read about it here](http://mirror.codeforces.com/blog/entry/11080)) is embedded at each node in a BIT. It only works if a 2D BIT has to be implemented for a grid of binary numbers (grid filled with only $1$ or $0$). The `update()` function has been broken into 2 functions — `insert()` (to insert a 1 in the grid at a given point) and `remove()` (to remove a 1 from the grid). The `query()` function counts number of 1s in the subgrid from $(1, 1)$ to any given position in the grid.↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
#define mp make_pair↵
using namespace std;↵
using namespace __gnu_pbds;↵
typedef pair<int, int> pii;↵
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> OST;↵
↵
const int N = 100001;↵
↵
OST bit[N];↵
↵
void insert(int x, int y)↵
{↵
for(int i = x; i < N; i += i & -i)↵
bit[i].insert(mp(y, x));↵
}↵
↵
void remove(int x, int y)↵
{↵
for(int i = x; i < N; i += i & -i)↵
bit[i].erase(mp(y, x));↵
}↵
↵
int query(int x, int y)↵
{↵
int ans = 0;↵
for(int i = x; i > 0; i -= i & -i)↵
ans += bit[i].order_of_key(mp(y+1, 0));↵
return ans;↵
}↵
~~~~~↵
↵
Time complexity : $O(Q log^2(N))$↵
<br>Space complexity : $O(Q log(N))$↵
↵
Problems : [Anton and Permutation](http://mirror.codeforces.com/contest/785/problem/E), [DISTNUM](https://www.codechef.com/problems/DISTNUM)↵
↵
PS: Suggestions are welcome. Please notify if there are any mistakes.
<br>1. Insert a $1$ in the grid at any position↵
<br>2. Remove a $1$ from any position in the grid↵
<br>3. Count the number of $1$ in a subgrid (ie. any rectangle inside the grid).↵
<br>Initially the grid is empty and there are $Q$ queries. ↵
↵
This can be solved easily by using a 2D BIT. But the conventional 2D BIT has space complexity $O(N^2)$. So if $N <= 10^5$, this won't work. Hence a compressed version of 2D BIT is required. This problem can be solved with an Implicit Treap along with BIT, but the implementation would be too complex. Here is an easy way to solve such a problem.↵
↵
In this implementation an Order Statistics Tree ([read about it here](http://mirror.codeforces.com/blog/entry/11080)) is embedded at each node in a BIT. It only works if a 2D BIT has to be implemented for a grid of binary numbers (grid filled with only $1$ or $0$). The `update()` function has been broken into 2 functions — `insert()` (to insert a 1 in the grid at a given point) and `remove()` (to remove a 1 from the grid). The `query()` function counts number of 1s in the subgrid from $(1, 1)$ to any given position in the grid.↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
#define mp make_pair↵
using namespace std;↵
using namespace __gnu_pbds;↵
typedef pair<int, int> pii;↵
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> OST;↵
↵
const int N = 100001;↵
↵
OST bit[N];↵
↵
void insert(int x, int y)↵
{↵
for(int i = x; i < N; i += i & -i)↵
bit[i].insert(mp(y, x));↵
}↵
↵
void remove(int x, int y)↵
{↵
for(int i = x; i < N; i += i & -i)↵
bit[i].erase(mp(y, x));↵
}↵
↵
int query(int x, int y)↵
{↵
int ans = 0;↵
for(int i = x; i > 0; i -= i & -i)↵
ans += bit[i].order_of_key(mp(y+1, 0));↵
return ans;↵
}↵
~~~~~↵
↵
Time complexity : $O(Q log^2(N))$↵
<br>Space complexity : $O(Q log(N))$↵
↵
Problems : [Anton and Permutation](http://mirror.codeforces.com/contest/785/problem/E), [DISTNUM](https://www.codechef.com/problems/DISTNUM)↵
↵
PS: Suggestions are welcome. Please notify if there are any mistakes.
