Does only studying Segment tree cover all Range query questions? (URGENT ANSWER Reqd., TY!)

Revision en3, by codesniper99, 2023-07-26 14:06:54

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

Tags segment tree, question, help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English codesniper99 2023-07-26 14:06:54 6
en2 English codesniper99 2023-07-26 14:06:35 16
en1 English codesniper99 2023-07-26 14:05:42 1194 Initial revision (published)