Блог пользователя ajaytank

Fenwick tree problem
Автор ajaytank, 10 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 5   Проголосовать: нравится -8 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 .

      → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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
          → Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

A simple 2D Fenwick tree can solve this problem.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

      → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        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.

        → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        → Ответить
»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

No any ideas?

→ Ответить