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

Interesting problem, multiple solutions

I came across a rather interesting problem: “Find a permutation of numbers 1 through N such that average of any two numbers in the permutation does not occur between them”. I found this problem particularly interesting because it lends itself to several different solutions.

Continue reading

Range updates with BIT / Fenwick Tree

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:

Continue reading

Scheduling to minimize lateness

The problem can be stated as follows :

“Given a set of n jobs all of which must be scheduled on a single resource such that all jobs arrive at time s and each job has a deadline di and a length ti, minimize the maximum lateness of the resulting schedule.”

We need to assign a start time si to each job i. Jobs are allowed to be late i.e., a job i may finish at time fi = si + ti > di. If job i is late, its lateness is defined to be li = fi – di. Otherwise, li = 0. So the objective is to find a schedule that minimizes the maximum lateness, L = maxi li.

Continue reading

Articulation Points or Cut Vertices in a Graph

A vertex in an undirected connected graph is an articulation point (or cut vertex) iff removing it (and edges through it) disconnects the graph. It can be thought of as a single point of failure. Any graph that contains an articulation point is inherently fragile because deleting that single vertex causes a loss of connectivity between other nodes. If a graph does not have an articulation point, then it is said to be biconnected.

Continue reading