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

Автор KiAsaGibona, 12 лет назад, По-английски

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
  • Проголосовать: не нравится

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +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.

  • »
    »
    12 лет назад, скрыть # ^ |
    ← 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

    • »
      »
      »
      12 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +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...

  • »
    »
    12 лет назад, скрыть # ^ |
    ← 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

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 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.

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

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

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

      that n in maxn because it makes a ballaced tree

      • »
        »
        »
        »
        12 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 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 :)

        • »
          »
          »
          »
          »
          12 лет назад, скрыть # ^ |
           
          Проголосовать: нравится 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
          
          
  • »
    »
    6 лет назад, скрыть # ^ |
    ← 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??

»
11 лет назад, скрыть # |
 
Проголосовать: нравится +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