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

How to use Binary Indexed Tree for Range Min/Max Query?
Автор KiAsaGibona, 10 лет назад, По-английски

How can I solve this problem UVA Problem 11297 — Census using Binary Indexed Tree ?

Problem Description in Short : Given a 2D grid (500x500 at most), I need to process 2 types of query.

  • Change the value of grid[x][y] by Val
  • Output the maximum and minimum number of a sub rectangle of grid (x1,y1) to (x2,y2)

( considering every input is valid ) How can I solve this problem using Binary Indexed Tree? Also it will be a great hand if you help me to understand how Range Minimum or Maximum Query can be done by BIT.

Thanks in Advance :)

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

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I don't think we can solve this problem with Binary Indexed Tree (Fenwick Tree). We can use Fenwick Tree only in cases:

  • The update query is maximize (or minimize) query instead of changing value query (i.e grid[x][y]=max(grid[x][y],val) ).
  • The output query is maximum (or minimum) query of a subrectangle from (1,1) to (x,y) (not from (x1,y1) to (x2,y2) ).

However, we can solve this problem with SegmentTree 2D.

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

    Thank you I_love_tigersugar for your reply. However I found this problem under BIT category in this site (29 th problem), So I was wondering if it can be solved by BIT..

    Then I searched a little and found two blogs that has code that can do RMQ using BIT ( at least they say so). Although I could not understand them. Right now I am not home and with a little access to internet, but I will edit this comment and provide links of those blogs no sooner I get back home. :) Edit Blog Links

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

      Well... Actually it seems that you can use BIT for this problem. But you need a bit special BIT which allows you to calculate not invertible function. You can read more about it here (Russian). But you still can only maximize/minimize but not change...

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

    Ok, I_love_tigersugar I'm back in home again. I found these two blogs interesting,

    • habrahabr.ru This is a Russian site, but I translated it with google translator. This blog provide the following code. (But I request you all to visit the site for detail notations )
    class FenwickTree
{
private :
     vector < double > a;
     vector < double > left;
     vector < double > right;
 public :
     void PreProc();
     double Max( int left, int right);
     void Update( int i, double cost);
};

void FenwickTree preproc :: () {
  for ( int i = 0 ; i <a.size (); i ++) Update (i + 1 , a [i]);
}

void FenwickTree :: Update ( int R, Double cost)
{
    a [r- 1 ] = cost;
     int i = R;
     while (i <= pow ( 2.0 , Double (k)))
    {
        left [i] = max (left [i], cost);
        i = i + G (i);
    }
    i = r;
    while (i> 0 )
    {
        right [i] = max (right [i], cost);
        i = iG (i);
    }
}

Double FenwickTree :: Max ( int L, int R) {
     Double RES = 0 ;
     int i = L;
     while (i + G (i) <= R)
    {
        res = max (res, right [i]);
        i = i + G (i);
    }
    if (A [I- 1 ]> res) ans = i;
    res = max (res, a [i- 1 ]);
    i = r;
    while (iG (i)> = L)
    {
        res = max (res, left [i]);
        i = iG (i);
    }
    Return RES;
}
    • StackOverflow Which provides the following code. ( Again please click the link I tagged )
    int que( int l, int r ) {
    int p, q, m = 0;

    for( p=r-(r&-r); l<=r; r=p, p-=p&-p ) {
        q = ( p+1 >= l ) ? T[r] : (p=r-1) + 1;
        if( a[m] < a[q] )
            m = q;
    }

    return m;
}

void upd( int x ) {
    int y, z;
    for( y = x; x <= N; x += x & -x )
        if( T[x] == y ) {
            z = que( x-(x&-x) + 1, x-1 );
            T[x] = (a[z] > a[x]) ? z : x;
        }
        else
            if( a[ T[x] ] < a[ y ] )
                T[x] = y;
}

    Please help me to understand how they used BIT to calculate RMQ

    → Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится 
const int N = 1 << 17; // has to be power of 2
const int inf = 1 << 28;

struct RMQ {
    int a[N * 2];
    RMQ() {
        FOR(i, N * 2)
            a[i] = inf;
    }
    void SetMin(int pos, int x) {
        for (int i = pos + N; i; i >>= 1)
            a[i] = min(a[i], x);
    }
    int GetMin(int L, int R) const // [L, R) i.e. L <= i < R
    {
        int res = inf;
        for (L += N, R += N; L < R; L >>= 1, R >>= 1) {
            if (L & 1) {
                res = min(res, a[L]);
                L++;
            }
            if (R & 1) {
                R--;
                res = min(res, a[R]);
            }
        }
        return res;
    }
};

I copied goo.gl_SsAhv code from here.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится 
    const int N = 1 << 17; // has to be power of 2

    No. RMQ is commutative, thus N can be any number.

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

      that n in maxn because it makes a ballaced tree

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

        keyvankhademi Can you Please elaborate your answer.. And help me to understand the idea of the code above.

        The things I do not understand,

        • const int N = 1 << 17; // has to be power of 2 Why we set like it, why not set const int N = 1 << 18; or const int N = 1 << 19; or const int N = 100000;

        • At void SetMin(int pos, int x) we are iterating like for (int i = pos + N; i; i >>= 1) why we add N with pos, what's wrong if we do not add N with pos and just iterate like for (int i = pos; i; i >>= 1)

        • Also please describe the logic in this code portion

        for (L += N, R += N; L < R; L >>= 1, R >>= 1) {
            if (L & 1) {
                res = min(res, a[L]);
                L++;
            }
            if (R & 1) {
                R--;
                res = min(res, a[R]);
            }
        }

        Thanks in Advance :)

        → Ответить
        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится 
          I think you should learn trees at first
search for some trees like segment tree & BIT & binarySearchTree & ...

if N is power of two
1. pos + N shows the position of leaf pos in balanced tree
2. i >>= 1 shows parent of i
3. and each nonleaf node has exactly 2 children & the tree is balanced
thats why power of 2 is good :D but you can also use 1000 or 934324
but the code get much more complicated

and about that part of code: i think it moves L and R from their leaf node upward to calculate minimun in that range
          → Ответить
          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            but you can also use 1000 or 934324 but the code get much more complicated

            what balance you talking about? What will be much more complicated? For example, there is my submission 7938499 with such segment tree and N = 1000010 — not a power of 2.

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится 
              actually it depends..
i will correct my sentence "in some cases using balanced binary tree is better"
for example if you want find value of position i in your segtree you should use o(log n)
but in that code use o(1)
return tree[i+N];
              → Ответить
              • »
                »
                »
                »
                »
                »
                »
                »
                10 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Power of 2 has no advantages. Only memory waste.
                You can count all vertices that aren't in the last layer of tree and call it R. After that to have access to position i you need just to return tree[i + R].

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

            Thanks keyvankhademi.. Big Time :)

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

    your code takes R as R + 1. I used your code and when passing the parameter in GetMin I had to give R as R + 1. can you tell why??

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

i know that it's an old post , but today i just read a paper about RMQ with BIT so i decided to share it to everyone who are interested about this topic

http://ioinformatics.org/oi/pdf/v9_2015_39_44.pdf

→ Ответить