Hi, TLDR: Can I solve all kinds of range query questions (the kind with N, Q<= 100,000) by just studying Segment trees?? (O(logn) query and update questions)
My knowledge till now tells me that Segment trees can be used for range query problems, I haven't found any other application yet (O(logn) query and update)
Context: I have some interviews lined up in coming days, I have studied the Segment tree from Codeforces guide and have got some good understanding for first time in my life how to implement and solve questions.
Now I see there are more advanced Data Structures/techniques (I have no idea of) like:
- Fenwick Tree
- BIT (Maybe this is same as above idk_)
- Order Statistic Tree
- Square root decomposition
- Tries
etc..
Now I need to work optimally and can't spend time learning more about Fenwick, BIT, and other DS too. I wanted to ask are there kinds of range query questions which can't be solved by segment trees? Will I be forced to learn about the other DS to solve some random question which may come my way (which is range based)
Thanks in advance, Me
The Mo's algorithm cover some problems that segment tree can't.
No
There're a lot of quieries you can come up with and a lot of data strucutures for theses quieries. Segment tree supports all associative operations with neutral element. Fenwick Tree (BIT) supports only subset of these operations
What does neutral element mean? I never found that anywhere? I read about its use for associative operatons. If BIT can solve subset of segment trees, then segment trees can solve all of BIT problems is that correct?
neutral is such element A that for any B, A*B = B. 0 + 5 = 5, or min(INT32_MAX, 5) = 5 for example. Yes segment trees can solve all of BIT problems, BIT is just easier to implement and faster.
Ok I understand, yes I use this neutral element for such operations then. Can you give rough estimate of how much faster would it be to implement a BIT in your own experience (like 5%, 10%) For me implementing a segmentr tree takes around 10-15 mins after I've decided on the solution function. Is it worth learning (BIT?) then?
haha, for me it's much easier, but there're also short implementations of segment tree, so idk, let it be 100% faster =D. If you are in rush, then no worries about it, but of course I recommend you to learn it after, it's very cool data structure!
Yes
No, but I would rather recommend getting better at the basics instead of learning nontrivial data structures like segment trees — you don't really need segment trees until you hit 1900, or maybe 2100 these days.