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
Auto comment: topic has been updated by codesniper99 (previous revision, new revision, compare).
Auto comment: topic has been updated by codesniper99 (previous revision, new revision, compare).
The Mo's algorithm cover some problems that segment tree can't.
Can you share some good resources for Mo's algorithm? Do you think that it might be asked in interviews as potential solution? Personally I think Segment trees might be the limit as I have seen it asked in some of the OA's for companies im interviewing for
No
Why is that, care to elaborate? Which would be the extra DS I need to learn? Can a Segment tree cover all questions that a Fenwick Tree can be used to solve?
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!
Ok, thanks for your input, seems like I'll skip it for now. Even chatgpt says its good for just cumulative sum problems but segment trees can handle that also so... take care!
Yes
Someone mentioned about some Mo's algorithm that it covers problems which segtree dont. Is this true or false?
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.
I understand but this is so that I can clear the OA round of company interview. They asked question regarding segment tree last year, so was brushing on that. Now I feel confident If they give segment tree problem I can solve it in time (easyish segment tree) . Im just covering all bases so that atleast I know my tools. Then in the interview time I can think of how to use tools together. If I didnt know how to query in O(logn) I would never b able to think even
But thanks for your concern I understand