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.

Continue reading

Advertisements

Test oracle: A useful tool for competitive programmers

How often do you get stuck at a problem with no clue about what’s going wrong? You seem to be doing everything right, all the test cases that you’ve thrown at your code pass but still the judge spits out WA. If you are like me, I’d say it happens quite often and it’s very frustrating. If only you could find a failing test case, you could make some progress. In this post, I describe a simple way to find some failing test cases so that you don’t get stuck so easily.

Continue reading

A simple approach to segment trees

A segment tree is a tree data structure that allows aggregation queries and updates over array intervals in logarithmic time. As I see it, there are three major use cases for segment trees:

  1. Static segment trees: This is probably the most common use case. We preprocess an array of N elements to construct a segment tree in O(N). Now, we can query aggregates over any arbitrary range/segment of the array in O(log N).
  2. Segment tree with point updates: This allows us to update array values, one at a time in O(log N), while still maintaining the segment tree structure. Queries over any arbitrary range still occurs in O(log N).
  3. Segment tree with range updates: This allows us to update a range of array elements at once in O(N) in the worst case, however problem specific optimizations and lazy propagation typically give huge improvements. Queries over any arbitrary range still occurs in O(log N).

In this post, I’ll cover the first two use cases because they go together. Given a static segment tree, it is very easy to add point update capability to it. I’ll leave the third use case as the subject matter of a future blog post. I intend this post to be a practical introduction to segment trees, rather than a theoretical description, so it will focus on how we can divide a segment tree into its components, the working of each component and how we can separate the problem specific logic from the underlying data structure. We’ll build a template for a segment tree and then apply it to several problems to understand how problem specific logic can be cleanly separated from the template.

Continue reading