How to use Binary Indexed Tree for Range Min/Max Query?

KiAsaGibona's blog

By KiAsaGibona, 11 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 :)

binary indexed tree, range query, range update, help to solved, uva 11279

KiAsaGibona
11 years ago
17

Comments (16)

Show archived | Write comment?

I_love_tigersugar

11 years ago, hide # |

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

KiAsaGibona

11 years ago, hide # ^ |

← Rev. 2 →

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

adamant

11 years ago, hide # ^ |

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

KiAsaGibona

11 years ago, hide # ^ |

← Rev. 2 →

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

qinyuyang

7 years ago, hide # ^ |

why do you only have one sequence? https://ioinformatics.org/journal/v9_2015_39_44.pdf

→ Reply

Allanur

11 years ago, hide # |

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

CountZero

11 years ago, hide # ^ |

← Rev. 2 →

const int N = 1 << 17; // has to be power of 2

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

→ Reply

keyvankhademi

11 years ago, hide # ^ |

that n in maxn because it makes a ballaced tree

→ Reply

KiAsaGibona

11 years ago, hide # ^ |

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

keyvankhademi

11 years ago, hide # ^ |

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

CountZero

11 years ago, hide # ^ |

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

keyvankhademi

11 years ago, hide # ^ |

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

wackloner

11 years ago, hide # ^ |

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

KiAsaGibona

11 years ago, hide # ^ |

Thanks keyvankhademi.. Big Time :)

→ Reply

iabhishek15

6 years ago, hide # ^ |

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

→ Reply

safecomp

10 years ago, hide # |

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