Easy implementation of Compressed 2D Binary Indexed Tree for grid of binary numbers

Revision en4, by sdnr1, 2017-05-21 09:43:14

Suppose you want to solve a problem in which you have 3 types of queries in a grid of size N × N:
1. Insert a 1 in the grid at any position
2. Remove a 1 from any position in the grid
3. Count the number of 1 in a subgrid (ie. any rectangle inside the grid).
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(N2). So if N <  = 105, 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) 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(Qlog2(N))
Space complexity : O(Qlog(N))

PS: Suggestions are welcome. Please notify if there are any mistakes.

Tags binary indexed tree, 2d binary indexed tree, range query, range update

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English sdnr1 2017-05-21 22:59:54 138 Problems added
en6 English sdnr1 2017-05-21 09:47:43 10
en5 English sdnr1 2017-05-21 09:44:03 0 (published)
en4 English sdnr1 2017-05-21 09:43:14 8
en3 English sdnr1 2017-05-21 09:41:22 1568 Tiny change: 'f size $N x N$: 1 - I' -> 'f size $N \cross N$: 1 - I'
en2 English sdnr1 2017-05-21 08:35:46 260
en1 English sdnr1 2017-05-21 08:20:22 364 Initial revision (saved to drafts)