KiAsaGibona's blog

How to use Binary Indexed Tree for Range Min/Max Query?
By KiAsaGibona, 10 years ago, In English

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

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

Comments Comments (16)
| Write comment?
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

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

    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

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

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

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

    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

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
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.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
    const int N = 1 << 17; // has to be power of 2

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

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

      that n in maxn because it makes a ballaced tree

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

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

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it 
          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
          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it 
              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];
              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                10 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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].

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

            Thanks keyvankhademi.. Big Time :)

            → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 4   Vote: I like it -8 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply