OmaeWaMouShenDeiru's blog

RMQ using Binar Indexed Tree. ??
By OmaeWaMouShenDeiru, history, 9 years ago, In English

Hay codeforces, Is it possible to solve standard RMQ problem using binary indexed tree with conserving LogN queries ?

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

Comments Comments (4)
| Write comment?
»
9 years ago, # |
← Rev. 5   Vote: I like it +1 Vote: I do not like it

It can be done with Segment Trees (with the same complexity). Using segment tree from here.

struct segment_tree {
    int t[2*maxN];
    void build() {
        for (int i=n-1;i>0;--i)
            t[i]=min(t[i<<1],t[i<<1|1]);
    }
    int query(int l,int r) {
        int minV=inf;
        for (l+=n,r+=n;l<r;l>>=1,r>>=1) {
            if (l&1)  minV=min(minV,t[l++]);
            if (r&1)  minV=min(minV,t[--r]);
        }
        return minV;
    }
 
}
→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

With BIT you can only get the minimum value on the interval (1, r)

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

    You are mistaken. BIT (Binary indexed tree, Fenwick tree) can be modified for RMQ. I don't remember articles or blogs in English with this modification, but you can read the implementation here. PS. Sorry for my bad English :)

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

Thanks all :D

I solved this simple problem with this code, and the runtime was pretty good.

can any one please tell me the complexity of my code.

I didn't thought it would pass the time limit, but indeed it was pretty fast.

→ Reply