hriss95's blog

By hriss95, 11 years ago, In English

Hey guys, I have been solving this simple on first thoughts problem. I have been learning segment trees and I have some issues solving this:

We have an array of elements which are all 0 at first. Than we have 2 operations:

1) get sum f(l,r) of elements a[l], a[l+1], .... a[r-1], a[r]

2) change all elements in the interval L to R by value V

So I have solved the problem when the second operation is changing value of 1 element but when it is a range I have difficulties implementing that. So I hope some of you who are into segment trees will find that interesting and will be willing to help :)

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You must use lazy propagation

useful link

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, the idea is the same. Let each node have a value "add", which says by which number should we increase all the elements belonging to the range of that node. Let us have a query (a,b,val) which means we should increase all values from a to b inclusive by val. Let's do it recursively with function Add(a,b,val). If we come to a node which has has range (l,r) then
1) if (a > r) or (b < l) we stop processing that node since the query has nothing to do with the range of that node.
2) if (a <= l) and (b >= r) we increase the value "add" of that node by "val" since the query covers the range of the node.
3) else we call the same procedure with the same arguments (a,b,val) in the left and the right son.
In order to count the sum we should add some code lines in the end of the Add() function. Sum of the current node be the sum of the both sons plus their ("adds") * (size of their range). This may seem vague, but if get down to my code below and look at it once or twice you will get the idea quickly.

The Sum(a,b) function:
1) if (a > r) or (b < l) we stop processing that node since the query has nothing to do with the range of that node and return 0.
2) if (a <= l) and (b >= r) we return the sum which was stored already in that node plus its ("add") * (r-l+1).
3) else return L.Sum(a,b,val) + R.Sum(a,b,val) + (current "add")*(size of intersection between [a,b] and [l,r]) which equals (min(b,r)-max(a,l)+1).

Code on C#.
http://pastebin.com/X3UrHk1N

By the way many people implement this using standard arrays so I do not imply in any way that my Segment Tree in classes is the only correct implementation. Surf the internet to find the standard array implementation if you don't like classes :)

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you very much! I knew the theory on that one but I forgot to add the add values of the sons and I would get smaller sums for some nodes. Once again thank you :)

»
10 years ago, # |
  Vote: I like it -7 Vote: I do not like it

You can find a good tutorial on Segment Trees here. Good luck!