ajaytank's blog

Fenwick tree problem
By ajaytank, 10 years ago, In English

I am trying to solve the following problem but I am getting 'java.lang.OutOfMemoryError'

Problem statement:

Suppose we have a plane with dots (with non-negative coordinates). We make three queries:

1)add dot at (x , y)

2)count number of dots in rectangle (0 , 0), (x , y) — where (0 , 0) if down-left corner, (x , y) is up-right corner and sides are parallel to x-axis and y-axis.

total no.of queries is M and the constraint are as follow

0<x,y<=10^9;

0<M<=100000(=10^5);

the solution given in this topcoder tutorial uses tree[max_x][max_y] which is tree[10^9][10^9] and surely one will get 'out of memory' error.

I have tried to compress the value of x,y (mapping {1,2,3..} to input set) but still it takes 10^5*10^5 which is out of bound.

Plz tell me what is the right way to solve this kind of problem.

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

Comments Comments (20)
| Write comment?
»
10 years ago, # |
← Rev. 5   Vote: I like it -8 Vote: I do not like it

EDIT: O(n log^2 n) memory. Fenwick tree on map. (Zlobober pointed it out)

First, input all (x, y). Use map, set or binary search to compress numbers.

For example: (1, 10^9), (10^9, 1), (2, 2), it will become: (1, 3), (3, 1), (2, 2)

(x: 1, 10^9, 2 -> 1, 3, 2

y: 10^9, 1, 2 -> 3, 1, 2).

Comment if you think my post unclear. EDIT:

Sorry for not read the post carefully.

one of interesting/similar problems: http://stackoverflow.com/questions/15219782/counting-total-number-of-points-inside-2-circles

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

    It is clear but I have to define Array[3][3] (in your example) if i use the fenwick tree (method shown in topcoder tutorial)

    if I have 10^5 point then Array[10^5][10^5] will be out of bound.

    I think i am missing something that might be obvious.(I know only one method shown in link) Plz guide me

    I would be very thankful to you.

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

      You can use hashmaps and create Array[x][y] only when requested. Each query creates not more elements, so total time and memory usage is .

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

        Could you please give any example to make it more clear.. Thanks

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Warning: beware of probable bugs.

          Something like this:

          class FenwickTree
{
    private:
        unordered_map<ll, int> Fenw;
        // probably better solution is to specify
        // std::hash<pair<int, int> >
        int maxlen;

        ll ValOf(int x, int y)
        {
            return ((ll)x << 32LL) ^ y;
        }

    public:
        FenwickTree()
        {
            Fenw.clear();
            maxlen = 0;

            // create empty Fenwick tree
        }

        void init(int n)
        {
            Fenw.clear();
            maxlen = n;

            // we set maxlen to n, n <= 10^9 if we don't compress coordinates,
            // else n <= 10^5
        }

        // We assume field is [1, maxlen] X [1, maxlen]

        // sum on rectangle [1, x] X [1, y]
        int AngleSum(int x, int y)
        {
            int totalcnt = 0;

            for (int i = x; i > 0; i -= i & (-i))
            for (int j = y; j > 0; j -= j & (-j))
            {
                auto it = Fenw.find(ValOf(i, j));

                // If Fenw[i, j] is not created, value of it is zero
                if (it != Fenw.end())
                    totalcnt += (it -> second);
            }

            return totalcnt;
        }

        // Add val to value of square (x, y)
        void PointAdd(int x, int y, int val)
        {
            for (int i = x; i <= maxlen; i += i & (-i))
            for (int j = y; j <= maxlen; j += j & (-j))
                Fenw[ValOf(i, j)] += val;
                // probably some Fenw elements are created here
        }
};

          Example of Tests:

          FenwickTree Data;
Data.init(100 * 1000);

Data.PointAdd(2, 3, 12);
Data.PointAdd(224, 24, 13);
Data.PointAdd(1, 8, 1);
cout << Data.AngleSum(1, 1) << endl;
cout << Data.AngleSum(2, 3) << endl;
cout << Data.AngleSum(1, 8) << endl;
cout << Data.AngleSum(1000, 1000) << endl;

          Output (seems to be correct):

          0
12
1
26
          → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A simple 2D Fenwick tree can solve this problem.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Sure, OP already knew that; He just ask to optimize his program's memory.

    → Reply
»
10 years ago, # |
  Vote: I like it -17 Vote: I do not like it

It's not a Fenwick tree problem, it's a 2D segment tree problem. 'nuff said.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    You're wrong. 2D Fenwick tree can be implemented using O(NlogN) memory in the same manner as 2D segment tree.

    First you compress all coordinates and create array A[], where element A[x] is responsible for a vertical strip containing all points with x-coordinate between F(x) and x (F(x) is the function you prefer to use in Fenwick tree, for me it is x - (x & (x - 1)).

    Each element A[x] will be a Fenwick tree itself, responsible for its vertical strip. But it will have size equal to the number of elements in that vertical strip that is generally smaller than 105. You should also compress y-coordinates only for this segment. So, A[x] is a Fenwick tree along the vertical direction.

    It's easy to see that this structure contains elements, can be built in time and can answer queries of form "number of points in rectangle" in time. It's the fastest solution for this problem that I know. It's much faster than 2D segment tree.

    Obviously it's also much faster than implementing 2D-Fenwick on Map/UnorderedMap.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks a lot.

      So far I was storing every point in fenwick regardless of its value but I got that we don't actually need to store the point whose value is zero.

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

      Oh, I didn't realize it could be solved that way. I suppose the "compress y-coordinates only for this segment" includes maps with some elements total, so it doesn't have the awesome constant of BIT (and doesn't work online), but it should be pretty fast.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        It has even more awesome constant then BIT =)

        You don't need to use maps for compressing y-coordinates. Lets' store for each x also a vector with y-coordinates of this segment in increasing order. We can use this vector for comressing y-coordinates.

        Pseudocode of such structure:


        vector<int> A[N];
vector<int> order[N];

void build(vector<point> P)
{
  compress x-coordinates in P;
  sort P in order of increasing y-coordinate
  for point in P
  {
    for (x = point.x; x < N; x = (x | (x - 1)) + 1)
    {
      order[x].push_back(point.y);
      A[x].push_back(0);
    }
  }
}

// get sum in rectangle [0, w] x [0, h].
void get(int w, int h)
{
  int ans = 0;
  for (int x = w; x > 0; x &= x - 1)
    ans += get_v(x, h);
  return ans;
}

// get sum in rectangle (F(x), x] x [0, h]
void get_v(int x, int h)
{
  int ans = 0;
  h = upper_bound(order[x].begin(), order[x].end(), h) - order[x].begin(); // not sure here, double-check this formula
  for (int y = h; y > 0; y &= y - 1)
    ans += F[x][y];
  return ans;
  for (int y = h; y 
}

void add(int x, int y, int value); // this two functions are implemented
void add_v(int x, int y, int value); // in the same manner

        What do you mean by "it doesn't work online"? Usual 2D segment tree doesn't work completely online also.

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

          Online as in IOI 2013 Game. (if it had summation instead of GCD)

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

          I am not able to understand how it works? can anyone please explain this code? also what does A[x].push_back(0); in your code does. thanks!

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

            The vector is initially empty so we need to fill them with 0.

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

          hey can u explain F[x][y] term in your code. Thanks

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

      How will it take O(NlogN) memory? If N = 10^5, then even after coordinate compression there would be N values of x and y both.

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

        First of all, this thread is years old, so it is often frowned upon to "necropost" and bring it back to life.

        However, what Zlobober is saying is to compress the values within each position of the first layer tree. If we talk about tree[x][y], x is the position of the first layer. If we set an array of this size, you are correct — it will be too much memory. However, the amount of distinct 'y' values differs for different positions 'x'. We only need to assign memory to the order of how many items that will ever appear at 'x'.

        Now, suppose we have an item we want to insert into our structure. Its 'y' value will go into at most logN 'x' values clearly, and each time it goes into something it uses 1 piece of memory. So each for N insertions we use NlogN memory. We can use vectors to pre-process which 'y' values show up at a certain 'x' value. Therefore, we avoid creating the whole 2D array.

        I hope this is clear.

        → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Maybe someone could help me with Fenwick tree problem too?

If we use simple Fenwick tree for finding sum, and every element of initial array is 0 or 1, and we have 2 type of queries:

1) replace given "1" to "0" value (and only 1->0 replacements, so, count of "1" decreases every time)

2) find position of K-th "1" in the array

So, "1)" could be done in O(log2(N)), and what about "2)"? How to make second query in O(log2(N)) time too, not in O(log2(N)^2) ?

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

No any ideas?

→ Reply