A simple approach to segment trees, part 2

This post is in continuation to a previous post on segment trees. If you haven’t read that post already, it would be a good idea to read that first.

Let me do a quick recap. The previous post described three use cases for segment trees (persistent/static, point updates and range updates) and explained the first two, leaving the last as the subject matter for this post. This post will describe how we can use range updates with segment trees, lazy propagation and various optimizations possible.

I tried to come up with a single template for segment trees which supported all the 3 use cases, had lazy propagation and all the optimizations that come with it but finally I decided it wasn’t worth the effort for following reasons:

  • The more general I made the template, the slower it ran. Most problems which require segment trees with lazy propagation have very strict time constraints on online judges and I had to run through hoops and do some serious gymnastics to get the solutions to pass.
  • Supporting different flavors of lazy propagation and various optimizations places huge requirements on the SegmentTreeNode (described in previous post), requiring it to implement as many as 10 functions for any problem. I guess there comes a point when the cure becomes more harmful than the disease.
  • Pretty much every new problem required me to generalize the template in some way or add more functions to SegmentTreeNode. This became unusable pretty soon.

For these reasons, I decided that different ideas in lazy propagation and various optimizations that come with it are hard to combine, to say the least, and probably not worth the effort. So I’ll take a different approach. I’ll start with a partial template and fill bits and pieces of it to demonstrate different ideas.

We now only have to describe how to fill in update() and query() methods.

The previous post provided us a way to update a single element in O(log N) time. We can use it to achieve range update in O(N log N) by calling the point update function iteratively for each element in the given range. But we can do better! We can in fact do a range update in O(N). The range update function is very similar to the buildTree() function.

This along with the query() function defined in the previous post allows us to do range updates in O(N) and range queries in O(log N). Note that this requires us to add a function void applyUpdate(UpdateType value) to our SegmentTreeNode.

Let’s see it in use on a sample problem.

Problem:

Given an array A of N floating point values, support two operations on any range A[a..b] (0<=a<=b<N):

  • replace each A[i] (a<=i<=b) by sqrt(A[i])
  • find sum A[a]+…+A[b]

Solution: The SegmentTreeNode for this problem looks like this:

The complete solution for this problem is available here.

For most problems, however, we can’t get away with an update function having linear complexity and must do better. This is where lazy propagation comes in. The basic idea of lazy propagation is to hold off propagating updates down the tree and propagate them only when absolutely necessary. Lazy propagation can be built into any of update() or query() functions but here I’ll describe it only for update(). There are several reasons for why we might be able to hold off updates in internal nodes:

  • Some updates are not really required and can be thrown away. Doing nothing is awesome!
  • For some problems, updates can be applied to internal nodes (segments/ranges) as opposed to leaves (actual array elements).
  • For some problems, updates can be accumulated in internal nodes until they cross a threshold and only afterwards must they be propagated.

Let’s see some examples of these ideas on actual problems.

Problem (GSS4):

Given an array A of N integers, support two operations on any range A[a..b] (0<=a<=b<N):

  • replace each A[i] (a<=i<=b) by floor(sqrt(A[i]))
  • find sum A[a]+…+A[b]

Solution:

There is only a small difference between this problem and the previous one and that is that all array elements are guaranteed to be integers, even after applying updates. This provides us an opportunity for optimization: There’s only so many times you can take square root before a number reduces to 1 and once a number reduces to 1, it stays 1 forever. So, we can throw out updates for nodes which are 1. This problem demonstrates the first idea that we can sometimes throw away updates.

We can modify the update() function such that at each internal node, it decides whether to propagate an update or throw it out. The query() function remains unchanged.

I’ve tried to make the update() function as general as I could so that it works for several similar problems, without requiring any change. However, this requires 5 new functions to be implemented in SegmentTreeNode, although they are all 1-liners. The SegmentTreeNode for this problem looks like this:

The complete solution for this problem is available here. Note that I had to define the nodes[] array outside the SegmentTree template. The time limit on this problem is too strict to allow memory allocation/deallocation per test case.

Problem (HORRIBLE):

Given an array A of N integers, support two operations on any range A[a..b] (0<=a<=b<N):

  • add a given value v to each A[i] (a<=i<=b)
  • find sum A[a]+…+A[b]

Solution:

This problem demonstrates the second idea: for some problems, updates can be applied to (or stored inside) internal nodes. Any node whose segment is completely covered by the update segment can just store the update value and not propagate it down the tree. The query() function, while coming back up the tree, picks up pending updates and applies them to the result.

The SegmentTreeNode for this problem becomes:

Note how this change places special requirement on the merge() function. When we store an update inside an internal node, we ensure that queries to all other nodes (its ancestors and descendants) return correct results by:

  • modifying the query() function such that it collects pending updates while going back up the tree (recursion unrolling). This ensures that all descendants of a node will see an update made to that node.
  • modifying the merge() function such that update() function correctly updates all ancestor nodes of an updated node while going back up the tree (recursion unrolling).

The complete solution for this problem is available here.

Problem (FLIPCOIN):

Given an array A of N booleans, support two operations on any range A[a..b] (0<=a<=b<N):

  • flip each A[i] (a<=i<=b)
  • count how many of A[a],…,A[b] are true

Solution:

This problem is exactly similar to the previous problem. Here also, we can store updates in internal nodes, modify the merge() function to correctly update ancestors and query() function to correctly update descendants. The SegmentTree template for the previous problem can be used exactly as is for this problem. The only change is to SegmentTreeNode:

The complete solution for this problem is available here.

I hope this post provided a good introduction to range updates and lazy propagation in segment trees. There are some ideas that I’ve skipped, which are either very similar to what is discussed in this post (like lazy propagation in query() instead of in update()) or are rare (like holding off updates in internal nodes, until they cross a threshold, after which they should be lazily propagated). Both of these are natural extensions of what is described in the post. There may also exist some other ideas that I’m not yet aware of. Please share your thoughts, feedback and suggestions in comments.

20 thoughts on “A simple approach to segment trees, part 2

  1. Pingback: A simple approach to segment trees | Everything Under The Sun

  2. The explanation is excellent. Best i know on web .
    Please , if possible , give an example on lazy propagation on query and that of internal nodes with threshhold concept .

  3. How can we change the value of a range [x,y] to v , in logarithmic time? Eg, 1 4 7 would mean changing the values of all elements in indices 1 to 4 to 7.

    • We can achieve this through lazy propagation. We’ll lazily propagate the updates, stopping at the first segment that is completely covered by the update range and storing it there. Then, while querying if we go down that path, we can propagate the update downwards, essentially hiding the update time behind several query calls.

  4. How can we multiply each element of a range [x,y] by v , in logarithmic time? Eg, 1 4 7 would mean multiplying the values of all elements in indices 1 to 4 by 7.

  5. Hey Kartik, don’t you think that in FLIPCOIN, it’s nicer that the value would be a tuple with (#heads, #tails)? or (#heads, #total)? this way, the merge function would be self-contained.
    Note that in your code, you break the encapsulation of “merge” and outside it you handle the total number of coins:

    result.start = leftResult.start;
    result.end = rightResult.end;

    WDYS?

    • Hey, in your earlier comment, you said that storing segment start and end indices in SegmentTreeNode is better for encapsulation and code reuse. In this problem, there’s added benefit to storing them in the node because we needed them to calculate the statistics.

      I didn’t understand a few things about your question. Are you saying that the argument of assignLeaf() and addUpdate() should remain a boolean value but we should store the number of heads & tails in each node? Isn’t what is done almost the same? count stores the number of heads and we use (end-start+1) to calculate the total number of coins.

    • When we store start and end indices in SegmentTreeNode, we don’t have to pass those as arguments to query() and update() methods. Basically these are two ways to accomplish the same thing:
      1. Either you pass the start and end indices of the current interval to query() and update() methods, which looks more messy.
      2. Or store the start and end indices in the node itself and then you only have to pass the node index to these methods. It has added benefits if a node has to use the start and end index values for query or update (for an example, look at the solution of the problem HORRIBLE).

  6. can you please give a link to the question in which we have to use the third idea ?
    i.e. in which updates can be accumulated in internal nodes until they cross a threshold and only afterwards must they be propagated.

    • I’m sure there will be many problems that utilize this concept. A sample problem that I was able to think of: Given an integer array, support two operations: adding an integer to every element in a segment and querying how many elements are larger than X (a constant) in a segment. For this problem, we could store two values in each node: maximum value of any element in this segment and the sum of pending updates. Until the max + updates reaches X, we don’t have to propagate updates.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s