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

Правка en3, от 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

Теги segment tree, question, help

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский codesniper99 2023-07-26 14:06:54 6
en2 Английский codesniper99 2023-07-26 14:06:35 16
en1 Английский codesniper99 2023-07-26 14:05:42 1194 Initial revision (published)