codesniper99's blog

Does only studying Segment tree cover all Range query questions? (URGENT ANSWER Reqd., TY!)
By codesniper99, history, 16 months ago, In English

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:

  1. Fenwick Tree
  2. BIT (Maybe this is same as above idk_)
  3. Order Statistic Tree
  4. Square root decomposition
  5. 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

  • Vote: I like it
  • -25
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

The Mo's algorithm cover some problems that segment tree can't.

→ Reply
»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

No

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          16 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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!

          → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply