sdnr1's blog

By sdnr1, history, 7 years ago, In English

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))

Problems : Anton and Permutation, DISTNUM

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

  • Vote: I like it
  • +48
  • Vote: I do not like it

| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you please add a few practice questions. Thanks for the post!

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sdnr1 (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Tried solving this Problem, using simple 2D Fenwick tree using map<pair<int,int>,int> as tree. Also with order statistics implementation, but both give TLE. Whereas, using Merge Sort tree gives AC. ( Merge sort tree is basically, a segment tree where each node of tree keeps sorted array of interval it manages. ). Aren't all these supposed to be $$$O(log^2(N))$$$ per query? Is there a large constant for BIT and Order Statistics tree?

2D BIT attempt

OST attempt

Segment Tree AC

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Your 2D BIT implementation looks $$$O(\log^3(n))$$$ since you have two loops in the BIT code, plus another log factor from accessing the map. You could switch to a hashmap (you'd have to write your own hash function), it may (or may not) be faster in practice.

    Your OST code should be $$$O(\log^2(n))$$$ per query, but I think the issue is that the input to the problem can have values like $$$L_1 = 0$$$ which makes your BIT code loop indefinitely. Try setting the maximum N to 100010 or so, and add +2 to every incoming value (pairs and queries) (the +2 is because we want $$$L_1 - 1 > 0$$$ as well).

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I had tried unordered_map ( with custom hash )during the contest yesterday, but that too gave TLE. Also, I had posted the same comment on another blog here, where I realised the same thing, my implementation of BIT wants $$$1$$$ based indexing. I tried $$$+1$$$ to every input with $$$N$$$ set to $$$100005$$$, but I don't see why $$$+2$$$ and $$$N$$$ set to $$$100010$$$ would do anything different?

      Oh, we want $$$L1-1 > 0$$$ because we subtract those while getting a rectangle not starting at $$$(0,0)$$$. Cool, I'll try it now.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This is giving WA for some reason. The only thing I can think of is, OST keep unique values, and problem doesn't mention that all input points will be distinct.

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        One more thing: with $$$1$$$ based indexing the highest value is now $$$N$$$, so in your insert code the condition i < N isn't really correct anymore. Since we add +2, that loop should run with i <= 100002. Finally the problem doesn't say anything about the points being distinct/unique. So instead of a set of pairs {y, x}, you might want to use a map that maps y to some counter. Then you don't have to store the x or worry about duplicate points.

        EDIT: As in:

        using OST = tree<int, int, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Okay, but how to get count of all $$$y <= B$$$ in this case?