Solving UVa 11402 with Segment Trees

Pirate

UVa 11402: Ahoy, Pirates! is one of the most challenging of the uHunt starred problems I have come across so far, for a few reasons:

The problem is designed to be solved using a segment tree. This is a data structure that comes up in competitive programming, but isn’t covered in the standard algorithms textbooks (e.g., Sedgewick or CLRS). So I studied it for the first time in preparation for solving this problem.
A static segment tree like the one described in Wikipedia, is not sufficient. Solving this problem requires a segment tree that implements lazy propagation so that updates can be made efficiently.
As an extra challenge, the problem author added the requirement for an “invert” operation. This adds some implementation complexity and means a generic segment tree implementation won’t work.
Java solutions seem to run very close to the time limit, which is a generous five seconds for this problem. Even an efficient solution that addresses the previous points may nevertheless need some additional performance tweaking to run fast enough.

Read on for solutions to these issues, and an explanation of how to go about coding a solution.

The Problem

Ahoy, Pirates! asks you to construct binary strings and then answer questions about them.

Constructing the binary strings

Each test case in the input file starts with some information about the strings you’ll be using in that test case. The case starts with an integer M followed by M pairs of lines. The first line in each pair has an integer T, and the second line has a binary string fragment. For each of the M pairs, you need to concatenate T copies of the string fragment. When you make it through all of the pairs, you’ll have the final string.

Here’s a section from the first example test case:

These instructions tell you to concatenate 10 five times, followed by 1000 two times, which produces the binary string 101010101010001000.

Modifying and querying the binary strings

After the instructions for creating the binary string, the test case provides an integer Q that indicates the number of operations and queries that follow. For each of Q lines, there is a capital letter and a range (start position and end position) in the string.

There are three operations that modify the binary string:

E: set the digits in the range to 0
F: set the digits in the range to 1
I: invert the digits in the range

Finally, there is the query operation (S), which requires that you print the number of 1‘s in a range.

This problem can be solved efficiently using a segment tree.

Segment Tree

A segment tree is a data structure that is designed to efficiently answer questions about ranges in an array. For an array of integers, a segment tree is often used to answer these questions about the elements in a range:

What is the minimum value?
What is the maximum value?
What is the sum?

These questions can be answered easily by simply iterating through the array, but that takes $O(m)$ time, where $m$ is the length of the segment. Once a segment tree is constructed, it can answer these questions in $O(log (n))$ time, where $n$ is the size of the input data. This is necessary when a problem uses a large array, long segments and/or a large number of queries.

The segment tree answers range questions efficiently by storing information about the underlying data in a binary tree. More precisely, it is a complete binary tree, meaning that each level of the tree is filled from left to right so that every level except possibly the last one is completely filled. A complete binary tree can be conveniently represented as an array. In this array, nodes are stored starting at position $1$, and the children of node $p$ are stored at positions $2p$ and $2p+1$. This is the same approach used for representing a binary heap.

Each node in a segment tree represents information about a segment in the underlying array. A segment is just a contiguous set of array elements. The root node (node 1) represents the entire array. The left child of a node represents the left half of the parent’s range, and the right child represents the right half. So nodes 2 and 3, the children of the root node, represent the two halves of the original array. The leaf nodes of the segment tree represent segments of length 1 — i.e., individual array elements.

A node can contain information that helps answer one or more of the questions listed above: the minimum value in the range, the sum of the elements of the range, or some other item of interest to the problem. For this problem, we only care about the sum.

Lazy Propagation

If the source data never changes, then the segment tree can be built once and never updated. For this problem, updates are mixed in with queries. Therefore, we need a way to keep the tree up to date while the underlying binary string changes. The problem is that keeping the tree completely up to date at all times eliminates all of the performance advantages of the tree, which means our solution will be too slow.

The solution is a technique called lazy propagation. Here’s the idea: nodes only need to be up to date when they are required to answer a query. At other times, we can just store reminders that updates may need to happen eventually. Implementing this idea is somewhat complicated, but I’ll explain it in more detail below.

Program Logic

With the general segment tree design in mind, we can now create a segment tree implementation that is specific to this problem.

Build

The first step is to build the initial segment tree, which represents information about the binary string before any changes have been made. Like most tree algorithms, this one relies on recursion.

build the segment tree
    accept a start node and its range
    store the nodes range and size
    if the node is a leaf node (range of size 1)
        set its sum to the single underlying value
    otherwise
        recursively build starting at the left child
        recursively build starting at the right child
        set sum to left child sum + right child sum

If the input binary string has length len, then you can build the segment tree by calling build and passing in (1, 0, len-1): the root node and its range. Remember that you can calculate the range of each child from the range of the parent. For the root, the children have ranges [0, len/2] and [len/2+1, len-1].

To store node information, the simplest approach is to use an array of Node objects. Each Node object can then track the endpoints of the range, the sum, and any other useful information. Alternatively, you can use separate integer arrays indexed by node position. For either of these approaches, it’s helpful to know that for a complete binary tree with $n$ nodes in the last level (i.e., $n$ elements in the source data), you must declare an array of size $2\cdot 2^{\log n} – 1$. In my implementation, I used a set of arrays, since I needed some extra performance.

Propagate

To use a segment tree in problems like this one, where the underlying data can change, we need a way to keep the tree up to date.

To do that, we need the concept of lazy propagation. Lazy propagation works by storing a pending value for each node. This value serves as a reminder that updates may need to happen in the future. Without lazy propagation, updating a node could require one or both of its children to be updated as well to keep the tree up to date. That would trigger an update to the node’s grandchildren, and so on to the bottom of the tree. To avoid this costly chain reaction of updates propagating through the tree, we just update the node and two pending values (for the left and right children). Instead of propagating these values immediately, we wait until we need the updated information. If we never receive a query that involves those nodes, then we never need to update them.

For this problem, the pending value can represent one of four actions on a range:

Do nothing: there is no pending value
Clear: Set all range elements to 0
Set: Set all range elements to 1
Flip: Set each range element to 0 if it is 1, and 1 if it is 0

Each of these actions has a different effect on the node’s range sum. These effects are encapsulated in the following method:

get range sum
    accept a node and an action
    return a sum based on the action
        do nothing
            return the existing sum
        clear
            return 0, since all the bits are 0
        set
            return the size of the range, since
            all the bits are 1
        flip
            return (range size - the existing sum),
            since the sum needs to be "reversed"

Since we’re updating the entire range, we can quickly calculate the sum without iterating through the individual range elements. If we’re setting the range to 0, then of course the sum is 0. For 1, the sum will equal the number of elements in the range. If we’re flipping each bit, then the sum will also flip, which we can calculate by subtracting the current sum (the previous number of 1‘s) from the number of elements in the range.

When we’re about to perform an update or query on a range, we need to first propagate any pending value to the nodes that are part of the range, so that we don’t lose any saved values. To do that propagation, we can use a helper function that knows how to change the data values for a single node. We’ll use a two-step process: update the sum on the target node, and then update the pending values for any child nodes:

change a node value
    accept a node and a value
    if the value is DO NOTHING, return
    get the range sum for this node and value
    update the nodes sum
    if we are not at a leaf node, set child pending values
        for clear or set, propagate the same action
        for flip, propagate the appropriate new action

For set and clear, we can just propagate the action directly. For example, if we clear all bits in a range, then the bits in the first half are cleared, and the bits in the second half are cleared. Therefore, the pending value for both child nodes gets set to clear. Propagating the flip action requires a bit of extra thinking. Since the outcome of a flip operation is different depending on what value it is operating on, we need to consider each child separately. In particular, we need to consider each child’s pending value, as follows:

If the previous pending value was clear, flip it to set.
If it was set, flip it to clear.
If it was flip, change it to do nothing.
If it was do nothing, change it to flip.

Here’s why these rules work: A pending value indicates that an operation needs to be applied on a node. If a node has a pending value of clear, then at some point we need to clear all of the bits in its range. But if we find that its parent has a flip value that needs to be propagated, we need to reverse that pending operation. So clear becomes set, set becomes clear, and flip becomes do nothing (flipping a bit twice returns it to its original value).

If a node has no pending value (its pending value is do nothing) then we don’t know anything about the values in its range. They could be any sequence of binary digits from the original string. So we set its pending value to flip, which essentially postpones the operation until a later time. Eventually we’ll end up at a leaf node, which can be modified directly and in constant time since it only has one value.

After all of that preparation, the propagate function is quite simple:

propagate from a node
    accept a node v
    if the pending value is DO NOTHING, return
    call change with v and the pending value
    reset the pending value to DO NOTHING

Update Range

Now that we know how to propagate pending actions, we’re ready to implement a range update, which is one of the fundamental operations of a segment tree. Normally the purpose of a range update is to update all of the values in a range to a single value. UVa 11402 adds the complication that we may need to flip the bits rather than just setting or clearing them.

To update a target range to a target value, we use these three steps, always starting with the root node:

update range
    accept a node, a target range, and a target value
    propagate the current node
    if the target range completely contains the node range
        change the current node value
        return
    if the target range overlaps the start or
    end of the node range
        recursively update each child node
        set the current node value to the sum of
        its child values

Range Sum Query

The last Segment Tree operation we need is the range sum query, which uses everything set up in the previous sections to efficiently return a count of the number of 1‘s in a range. We will always call the range sum query by passing in the root node and the target range:

range sum query
    accept a node v and a target range
    if node range includes the target range
        if pending value is SET, return the range size
        if pending value is CLEAR, return 0
    if the target range completely contains the node range
        propagate v
        return the sum value
    if the target range intersects the start
    or end point of the node range
        propagate v
        recursively find the sum of the target range,
        starting from left and right children
        return the left child sum + the right child sum
    if none of these conditions are true, return 0

Performance Tips

In my experience, most starred uHunt problems use a three-second time limit. There are also some that use one- or two-second limits. This problem has a five-second limit. Nevertheless, I had to do some performance tuning to get my Java implementation to complete in under the time limit. Here are some ideas on getting your code to run faster:

The test input for this problem seems to be very large, so it’s best to avoid copying it around more than necessary. For example, you might be inclined to use a List<Integer> to store your binary string, since you don’t know in advance how long it will be. If you do this, keep it in that format rather than converting it to an array. Alternatively, just declare a large enough int[] array before you start reading the input.
Saving your heap data in a collection of arrays with the same index is faster than using an array of Node objects, though it’s a bit harder to follow in the code.
I wrote some general tips for Java I/O performance in Why is Java I/O Slow?.
You can try to pinpoint bottlenecks in your code using the techniques described in Profiling Java Programs with VisualVM. However, keep in mind that the specific test data you choose can have a big impact on performance. For example, a large number of small test cases may require a different design than a small number of large test cases. For this problem, the implementation that I eventually got accepted ran slower on my local test data than did an implementation that hit the time limit.

For Further Reading

Although segment trees may not be a standard topic in Computer Science curricula, there is plenty of information about them online. Here are some sources for further reading:

Competitive Programming 3, Chapter 2 includes a section on segment trees, and the companion web site provides an implementation. However, the implementation doesn’t include range update, range sum query, or lazy propagation, so it’s really just bare minimum skeleton code for this problem.
Sedgewick’s Algorithms textbook doesn’t include any information about segment trees, but the companion book site does include an implementation by Ricardo Pacheco. I used this one as a starting point.
This post from On Algorithm Problems is an excellent editorial for this problem. It includes pictures and a C++ implementation.
This Java implementation by Desmond gave me some hints to get my solution to run in under 5 seconds.
The Wikipedia article on segment trees uses a book called Computational Geometry: Algorithms and Applications as its main source.

If you made it this far, you should have a good start on creating your own implementation. If you need some help after you have given that a try, you can find my implementation on GitHub.

(Image credit: Pascal)