4. Range queries

In this chapter, we consider the task of efficiently processing range queries in a list of numbers. Common range queries include calculating the sum of numbers in a given range and finding the minimum or maximum value in a given range. We use a simple and efficient data structure called a segment tree to process such queries.

Range sum queries

Let’s start with range sum queries. We have a list of numbers, and we need to calculate the sum of numbers in a given range. Let \(\textrm{sum}(a,b)\) denote the sum of numbers in a range from position \(a\) to position \(b\).

For example, consider the list \([5,8,6,3,2,7,2,6]\), where the positions are indexed from \(0\) to \(7\). Some range queries on this list are:

• \(\textrm{sum}(0,1)=5+8=13\)
• \(\textrm{sum}(2,4)=6+3+2=11\)
• \(\textrm{sum}(5,5)=7\)
• \(\textrm{sum}(0,7)=5+8+6+3+2+7+2+6=39\)

It is easy to process range sum queries in \(O(n)\) time, because we can just go through the range using a loop and add up the numbers. However, this may be too slow if there are many queries.

We can process range sum queries in \(O(1)\) time if we first create another list that contains all cumulative sums for the original list. A cumulative sum is the sum of all list values up to a given position. For example, the cumulative sums for the list above are \([5,13,19,22,24,31,33,39]\).

Using the cumulative sums, we can easily answer any query of the form \(\textrm{sum}(0,k)\), because we have already calculated answers to all such queries. To process a query of the general form \(\textrm{sum}(a,b)\), we can use the formula

For example, in the list above,

The above approach works well if the original list is never modified, but updating the elements becomes difficult. For example, if we change the first element in the list, this affects all cumulative sums. Thus, updating an element now takes \(O(n)\) time, which may be too slow.

Using the above techniques, we can process either updates or queries efficiently, but not both at the same time. Fortunately, there are more advanced data structures that allow us to process both updates and queries efficiently. Next, we will learn about a data structure called a segment tree that achieves this.

Segment trees

A segment tree is a tree data structure that stores the elements of a list and some extra values to help process updates and queries efficiently. Here is a sum segment tree for the list \([5,8,6,3,2,7,2,6]\):

We assume that the length of the list is a power of two. If it is not, we can add extra elements to the end of the list.

Each segment tree node stores the sum of elements in a range. The top node represents the entire list. The left child of each node represents the left half of the range, and the right child represents the right half. The leaves of the tree are the original list elements.

For example, in the segment tree above, the node with value \(22\) represents the sublist \([5,8,6,3]\) with sum \(5+8+6+3=22\). The left child of the node with value \(13\) represents the sublist \([5,8]\) with sum \(5+8=13\), and the right child with value \(9\) represents the sublist \([6,3]\) with sum \(6+3=9\).

We can calculate any range sum as a sum of \(O(\log n)\) values from segment tree nodes. For example, consider the sublist \([6,3,2,7,2,6]\) with sum \(6+3+2+7+2+6=26\). We can calculate this sum using two segment tree nodes:

The node with sum \(9\) represents the sublist \([6,3]\), and the node with sum \(17\) represents the sublist \([2,7,2,6]\). The total sum is \(9+17=26\).

When an element is updated, we update all segment tree nodes that contain that element. There are \(O(\log n)\) such nodes. For example, when we update the list value \(7\), the following nodes will be affected:

A segment tree for a list of \(n\) values has \(2n-1\) nodes. A convenient way to store these nodes is by using a list that contains the node values from top to bottom and left to right. For example, the representation for the segment tree above is:

Note that position \(0\) is not used, and position \(1\) represents the top node. The children of a node at position \(k\) are at positions \(2k\) and \(2k+1\), and the parent is at position \(\lfloor k/2 \rfloor\). This representation is similar to the standard way of storing a binary heap.

The following code shows how to implement segment tree operations:

class SumSegmentTree {
public:
    int n;
    vector<int> tree;

    SumSegmentTree(int size) {
        n = 1;
        while (n < size) n *= 2;
        tree.assign(2 * n, 0);
    }

    void inc_val(int pos, int add) {
        pos += n;
        tree[pos] += add;
        for (pos /= 2; pos >= 1; pos /= 2) {
            tree[pos] = tree[2 * pos] + tree[2 * pos + 1];
        }
    }

    int get_sum(int left, int right) {
        left += n; right += n;
        int sum = 0;
        while (left <= right) {
            if (left % 2 == 1) sum += tree[left++];
            if (right % 2 == 0) sum += tree[right--];
            left /= 2; right /= 2;
        }
        return sum;
    }
};

The constructor takes the size of the list and finds the smallest \(n\) that is a power of two. Initially each list element is \(0\). The inc_val function increases the value at position pos by add and updates the parent nodes in the tree. The get_sum function calculates the sum for the range from position left to position right by moving from bottom to top of the tree. Both the functions work in \(O(\log n)\) time.

The following code example creates a segment tree for the list \([5,8,6,3,2,7,2,6]\) and performs some range sum queries.

SumSegmentTree st(8);

st.inc_val(0, 5);
st.inc_val(1, 8);
st.inc_val(2, 6);
st.inc_val(3, 3);
st.inc_val(4, 2);
st.inc_val(5, 7);
st.inc_val(6, 2);
st.inc_val(7, 6);

cout << st.get_sum(0, 1) << "\n"; // 13
cout << st.get_sum(2, 4) << "\n"; // 11
cout << st.get_sum(5, 5) << "\n"; // 7
cout << st.get_sum(0, 7) << "\n"; // 39

Counting inversions

As the first application of segment trees, we consider the problem of counting the number of inversions in a list of \(n\) numbers. An inversion is a pair of list elements \((a,b)\) such that \(a>b\) and \(a\) comes before \(b\) in the list. For example, the list \([3,1,4,2]\) has three inversions: \((3,1)\), \((3,2)\), and \((4,2)\).

We create an algorithm that goes through the list from left to right and calculates, for each position, the number of inversions whose second element is at that position. For example, for the list \([3,1,4,2]\), element \(1\) appears in one inversion \((3,1)\) and element \(2\) appears in two inversions \((3,2)\) and \((4,2)\).

We use a segment tree to efficiently calculate the number of inversions. For simplicity, we assume that each value in the list is an integer between \(1\) and \(n\). For each such value, we keep a counter in the segment tree, which is initially set to \(0\). When we process a value \(x\) from the list, we first count how many values between \(1\) and \(x-1\) have already appeared in the list using a range sum query. This gives the number of inversions where the second value is \(x\). After that, we increase the counter at position \(x\) by one using an update query.

The following function returns the number of inversions in numbers:

long count_inversions(vector<int> &numbers) {
    int n = numbers.size();
    SumSegmentTree counts(n + 1);
    long total = 0;
    for (int i = 0; i < n; i++) {
        total += counts.get_sum(1, numbers[i] - 1);
        counts.inc_val(numbers[i], 1);
    }
    return total;
}

The function works in \(O(n \log n)\) time because it performs one \(O(\log n)\) time range query and one \(O(\log n)\) time update operation for each element in the list.

Now consider a more general situation where the input list can contain any numbers, not just numbers between \(1\) and \(n\). We can use the same algorithm as above with one change: before running the algorithm, we relabel the list elements so that they are between \(1\) and \(n\), keeping their relative order the same. This is always possible because there are at most \(n\) distinct elements. For example, for the list \([42,1337,5,42,5]\), the relabeled list is \([2,3,1,2,1]\). We can relabel the values in \(O(n \log n)\) time, so the time complexity stays the same.

More queries

Segment trees are powerful data structures because they can be used for many different kinds of range queries, not just sum queries. In fact, we can use segment trees for any associative binary operation \(\circ\), where \((a \circ b) \circ c = a \circ (b \circ c)\) holds for any elements \(a\), \(b\), and \(c\). Such operations include:

• sum and product
• minimum and maximum
• bit operations: and, or, and xor
• greatest common divisor

For example, here is a segment tree for processing range minimum queries:

Now, each node represents the minimum value in the corresponding range. For example, the top node with value \(1\) tells us that the minimum in the list \([5,8,6,3,1,7,2,6]\) is \(1\). Its children contain values \(3\) and \(1\), which correspond to the minimums of the sublists \([5,8,6,3]\) and \([1,7,2,6]\).

Here is an implementation of a minimum segment tree that supports updating a value and calculating the minimum value in a range:

class MinSegmentTree {
public:
    int n;
    vector<int> tree;

    MinSegmentTree(int size) {
        n = 1;
        while (n < size) n *= 2;
        tree.assign(2 * n, 0);
    }

    void set_val(int pos, int val) {
        pos += n;
        tree[pos] = val;
        for (pos /= 2; pos >= 1; pos /= 2) {
            tree[pos] = min(tree[2 * pos], tree[2 * pos + 1]);
        }
    }

    int get_min(int left, int right) {
        left += n; right += n;
        int res = tree[left];
        while (left <= right) {
            if (left % 2 == 1) res = min(res, tree[left++]);
            if (right % 2 == 0) res = min(res, tree[right--]);
            left /= 2; right /= 2;
        }
        return res;
    }
};

Besides processing range queries, there are other possible queries. For example, we can find the position of the first occurrence of the minimum element in \(O(\log n)\) time by using a binary search style approach:

The idea is to start the search at the root node and then go to the left or right child, depending on which node has the smallest value. If both nodes have the same value, we choose the left child to find the first occurrence.

Longest increasing subsequences

Segment trees can sometimes be used to speed up dynamic programming algorithms. As an example, we consider the problem of finding the longest increasing subsequence in a given list of numbers.

The problem is to find the longest sequence of numbers from left to right such that each number is larger than the previous one. For example, given the list \([3,1,5,2,4,8,5,3]\), one longest increasing subsequence is \([1,2,4,5]\).

We can use the following simple dynamic programming algorithm to find the length of the longest increasing subsequence in \(O(n^2)\) time:

int find_lis_length(vector<int> &numbers) {
    int n = numbers.size();
    vector<int> lengths(n);
    int max_length = 0;
    for (int i = 0; i < n; i++) {
        lengths[i] = 1;
        for (int j = 0; j < i; j++) {
            if (numbers[j] < numbers[i]) {
                lengths[i] = max(lengths[i], lengths[j] + 1);
            }
        }
        max_length = max(max_length, lengths[i]);
    }
    return max_length;
}

The algorithm above goes through the list and calculates the length of the longest increasing subsequence ending at each position. It does this by extending a previous increasing subsequence with the current value. The second loop checks all possible positions where the previous subsequence could end.

We can optimize the algorithm by using a maximum segment tree, which finds the optimal previous position more efficiently. The following code assumes that each list element is an integer between \(1\) and \(n\):

int find_lis_length(vector<int> &numbers) {
    int n = numbers.size();
    MaxSegmentTree lengths(n + 1);
    int max_length = 0;
    for (int i = 0; i < n; i++) {
        int length = lengths.get_max(1, numbers[i] - 1) + 1;
        max_length = max(max_length, length);
        lengths.set_val(numbers[i], length);
    }
    return max_length;
}

The value at position \(k\) in the segment tree stores the maximum length of a subsequence found so far whose last value is \(k\). When the current list value is \(x\), we find the maximum length of a previous subsequence whose last value is between \(1\) and \(x-1\) and add one to that value. After that, we update the segment tree. This algorithm works in \(O(n \log n)\) time.

As in the inversion counting example, we can extend the algorithm to arbitrary numbers by relabeling the list elements.

Alternative algorithms

Segment trees are a general tool that can solve many problems where there are other ad hoc textbook algorithms. For example, there are traditional algorithms for counting the number of inversions and finding the longest increasing subsequence that do not use segment trees.

A common way to count the number of inversions in \(O(n \log n)\) time is to use an extended version of the merge sort algorithm. There is also a traditional ad hoc algorithm that finds the longest increasing subsequence in \(O(n \log n )\) time using a greedy approach and binary search.

Our segment tree algorithms can be seen as more direct approaches because they simply go through the list and calculate the result for each position. Another benefit is that these algorithms are easy to extend. For example, with a simple change, we can also use the segment tree approach to calculate the total number of all increasing subsequences in a list.