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

Правка en5, от sdnr1, 2017-05-21 09:44:03

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.

Теги binary indexed tree, 2d binary indexed tree, range query, range update

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский sdnr1 2017-05-21 22:59:54 138 Problems added
en6 Английский sdnr1 2017-05-21 09:47:43 10
en5 Английский sdnr1 2017-05-21 09:44:03 0 (published)
en4 Английский sdnr1 2017-05-21 09:43:14 8
en3 Английский 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 Английский sdnr1 2017-05-21 08:35:46 260
en1 Английский sdnr1 2017-05-21 08:20:22 364 Initial revision (saved to drafts)