Блог пользователя idek_bro

Question about segment trees
Автор idek_bro, история, 2 года назад, По-английски

Does a segment tree provide any functionality other than storing the sums of sub arrays? Is the usage of unordered_sets to store the sums of subarrays from [0,0] to [0,n], to calculate the sum of the subarray [l,r] as [0,r]-[0,l-1] a valid alternative to segment trees?

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
2 года назад, # |
← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

Segment Trees also allow you to update values in $$$O(logN)$$$ time. Using Prefix Sums would not allow you to update values in $$$O(logN)$$$ time, because in the worst case, you'd need to change all $$$O(N)$$$ prefix sums (which happens when the first element in the array is changed).

→ Ответить
»
2 года назад, # |
← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

There is no such easy thing like prefix sums that can be used for finding minimum on segment. And the segment tree is one of the most easy and effective ways to do this. It also allows you to do tons of crazy stuff. For example, adding Fibonacci sequence on segment and then calculating sum on segment.

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Segment tree can store monoids

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why are you learning segment trees after you do 2 codeforces problems

→ Ответить