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.
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:
- 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).
- 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).
- 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.
I described implementation of BIT/Fenwick tree in an earlier post as a way of maintaining cumulative frequency table, which allows operations like updating any single element and querying sum of elements in a range [a…b] in logarithmic time. I recently found out that this is only one of the ways of using a BIT. A BIT can in fact be operated in one of three modes:
A min-priority queue is an abstract data structure that supports efficient query of the minimum element in a list of elements, insertion of elements and deletion of the minimum element. It can be implemented as a min-heap, providing access to the minimum element in O(1), deletion of the minimum element in O(log N) and insertion in O(log N) where N is the number of elements in the heap.
A BIT (Binary Indexed Tree) or Fenwick Tree is a data structure providing efficient methods for calculation and manipulation of the prefix sums of a table of values.