justwanttohack's blog

By justwanttohack, history, 4 months ago, In English

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?

 
 
 
 
  • Vote: I like it
  • +10
  • Vote: I do not like it

»
4 months ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

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).

»
4 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Segment trees can be used for a whole bunch of functions over array subsegments, for example, finding the GCD of a subarray, the minimum and the maximum, XOR/OR/AND etc. Ant it's all with $$$O(log N)$$$ update query. It is also possible to use segment trees for subarray increments/assigns (handling operations like "increment all elements from l to r by two").

It's also a popular structure in other algorithms, such as finding the LIS of the array in O(n log n) time. Not the most efficient approach to that particular problem, but it's good as an example.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Segment tree can store monoids

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    I thought it was a dumb question to ask as a specialist-expert, therefore I chose to create an alt. My bad.