Hay codeforces, Is it possible to solve standard RMQ problem using binary indexed tree with conserving LogN queries ?
# | User | Rating |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
Hay codeforces, Is it possible to solve standard RMQ problem using binary indexed tree with conserving LogN queries ?
Name |
---|
It can be done with Segment Trees (with the same complexity). Using segment tree from here.
With BIT you can only get the minimum value on the interval (1, r)
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 :)
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.