Eklavya's Blog

Generalizing Segment Trees

A segment tree is a data structure which stores an array of size and allows -time range queries and -time range updates on it. I devised a method of generalizing segment trees by expressing query outputs as elements of a monoid and update operations as functions. This generalization not only gave me conceptual clarity but also allowed me to write a segment tree C++ library that can be used for any application without modifying the code for queries and updates.

This article explains what a monoid is, and the intuition which led me to use these abstractions to generalize segment trees. I'll also explain how to perform range updates using lazy propagation.

Prerequisite concepts for this article:

  • What a segment tree is.
  • How to build a segment tree.
  • How to perform range queries on a segment tree.
  • How to perform point updates on a segment tree.

You can read about the above prerequisite concepts in the article on Segment Trees by codelucid.

Generalizing problems

Before we generalize segment trees, let's try to generalize some simple problems which can be solved using segment trees. These example problems are used throughout this article.

  1. Problem SUMREPL: You are given an array of numbers, indexed from 0 to . You will be asked to perform operations. Each operation will be one of the following:

    • given and , output .
    • given , and , replace by for all .
  2. Problem MINMAX: You are given an array of numbers, indexed from 0 to . You will be asked to perform operations. Each operation will be one of the following:

    • given and , output .
    • given and , output .
    • given , and , add to for all .
    • given , and , multiply by for all .
  3. Problem CHAROCC: You are given an array of strings, indexed from 0 to . Each string consists of lowercase English characters (a to z). The sum of the lengths of the strings is . You will be asked to perform operations. Each operation will be one of the following:

    • given integers and and character , output the number of occurrences of in the concatenation of .
    • given integers and and character , append to for all . For example, if is "car" and is 't', then should be changed to "cart".

You can see that in all these problems, we are given an array of size . The elements of the array can be anything: numbers, strings or something else. In these examples, there are 2 kinds of operations - queries and updates. In all operations, we're asked to operate on a subarray . We'll generalize these operations to 2 concepts - query function and update function.

Query function

In queries, we're asked to apply a function on . We'll call this function the 'query function'. In SUMREPL, this function is summation: .

In MINMAX, the query function is 'min' for some queries and 'max' for others. Instead, we can use the query function , which returns an ordered pair. For every query, we'll compute both min and max and return the appropriate part.

In CHAROCC, the query is parametrized by . So we'll compute the result for all lowercase English characters. Formally, let be the sequence of characters in lowercase English and let be the number of occurrences of the character in string . Then . Here is an array of length 26.

For these 3 examples, we now have a common abstraction to use: the query function. The query function's domain is a set of finite arrays of some type. Let us denote the codomain of the query function by , which we'll call the 'query output type'.

Update function

In every update operation, we're given a function , called the update function. We have to replace by for .

For SUMREPL, the update function is , where . For MINMAX, the update function is either or .

Now the generalized problem looks like this:

Problem RANGEOP: You are given an array of elements, indexed from 0 to . You are also given a query function . You will be asked to perform operations. Each operation will be one of the following:

  • given integers and , output .
  • given integers and and a function , replace by for all .

Generalizing the query function

In problem RANGEOP, can be any arbitrary function. But there are additional constraints if the problem has to be solved using segment trees.

Substructure and the binary operator

To be able to solve a problem using segment trees, the query function should follow a property called 'substructure'. This means that we can compute using this procedure:

  1. Choose any prefix of . Let , where denotes array concatenation.
  2. Compute and .
  3. Combine and to get .

Examples:

  • In SUMREPL, .
  • In MINMAX, . Here and .

Non-examples:

  • Finding the median of an array doesn't have substructure because the medians of and cannot be used to compute the median of .
  • .

We can express the substructure recurrence relations using a binary operator , so that . is a function from to , where is the output type of the query function.

  • For SUMREPL, .
  • For MINMAX, .
  • For CHAROCC, is obtained by element-wise addition of arrays and .

Associativity

Depending on which prefix of we choose, there can be multiple ways of computing . For example, there are 2 ways of computing :

  • choosing as prefix:
  • choosing as prefix:

Since the output should not depend on the choice of prefix, should be associative over the range of .

Since is associative, .

Identity

Let's define . Since and , we call the 'identity element' of for .

may not be defined for an empty array; for example . When this happens, we can still define . need not have any real significance; it is just a symbol (this is similar to how ). We also define for all .

Monoids

A monoid is a set along with a binary operator defined on that set which follows these axioms:

  • Closure:
  • Associativity:
  • Existence of identity: . Here is called the identity of the monoid.

We can see that our query output type and our binary operator follow the above axioms. Therefore, is a monoid. We'll call it the 'query monoid'.

Monoid elements as segment tree values

Every node of a segment tree represents a segment (contiguous subarray) of the input array. For example, the root represents the whole array, the root's children represent the left and right halves of the array, and the leaves represent segments with only one element in them. Let's denote 's segment by .

In every node of the segment tree, we will store the value . Let's denote this by .

To build and query a generalized segment tree, we will need to specify the following:

  • : The identity element of the query monoid. This is the output of empty queries. For SUMREPL, . For MINMAX, .

  • : Specification of how to apply to a single-element array. This is used to create leaf nodes of the segment tree. For SUMREPL, . For MINMAX, .

  • : The binary operator. This is used to create internal nodes of the segment tree. For SUMREPL, . For MINMAX, .

C++ example

When we write a generic segment tree library in C++, we can make the query monoid type a template parameter.

Here's an example of how to represent query monoid elements as a class for the MINMAX problem:

#include <algorithm>

class MinMaxElem {
public:
    static const int infty = 2e9;
    int x_min, x_max;

    MinMaxElem():
        // identity element
        x_min(infty), x_max(-infty) {}

    explicit MinMaxElem(int x):
        // element at leaf node
        x_min(x), x_max(x) {}

    MinMaxElem(const MinMaxElem& l, const MinMaxElem& r):
        // binary operator
        x_min(std::min(l.x_min, r.x_min)), x_max(std::max(l.x_max, r.x_max)) {}

    MinMaxElem(int _x_min, int _x_max):
        // direct constructor (will be used later, when coding update functions)
        x_min(_x_min), x_max(_x_max) {}
};

In the segment tree library, we can call the above methods on the templated query monoid type without needing to know what they do.

Node update function

Suppose I construct a segment tree on the input array of size (where the query function is and the corresponding binary operator is ). Let the value at the root be . We know that . Now I apply a function to all elements of . For notational convenience, let . After this, I update the segment tree and the value at the root is now .

Given and , can you find ? This question effectively means that you should be able to update a segment tree node without looking at its descendants. We're looking for a function where for all arrays . Let's call a 'node update function'.

There's no straightforward algorithm for deriving from , but it's usually easy. For example, for the MINMAX problem with , . This is how we verify :

Here is the array obtained by adding 20 to every element of .

It can be proven that every node update function is an endomorphism (a homomorphism whose domain and codomain are the same). I'm omitting the proof here for brevity.

Lazy propagation

In computer science, laziness means procrastination.

When we're told to execute an update on a segment tree, we don't actually do the whole update. We just note down which subtrees need to be updated. Then when we're supposed to answer a query, we update only the part of the segment tree which is needed to answer the query.

I'll explain this with an example for MINMAX with the initial array . The image below shows the initial segment tree. It presents 2 attributes of every segment tree node :

  • the indexes of the first and last elements of .
  • .
segment tree on 7 elements
Initial segment tree

Updation

Now we get an update with . This corresponds to . Define . Therefore, .

To execute this update, we first find the maximal subtrees which span this range. These are the subtrees at 2..3 and 4..6. We'll update the values at 2..3 and 4..6 by applying to their values. We'll then note down that their children are yet to be updated with . We'll also update all the ancestors of the affected nodes by recomputing their values.

segment tree after adding 20 to 5 elements
Segment tree after update $l=2, r=6, g(x) = x + 20$.
Blue nodes were updated. Red nodes were not updated but they have a pending update.

Querying

If a query arrives for , we would like to return . But before that, we'll have to update . To do this, we apply to and mark its children as pending for updation. Since the pending update moved from 4..5 to its child, we say that the pending update 'propagated'.

querying a segment tree with lazy propagation
Segment tree after the query $l=2, r=5$.
The value returned by the query is written beside each node.

Combining updates

Suppose we get the update . We will update the root node and add to the children.

segment tree after two updates
Segment tree after update $l=0, r=6, g(x) = x + 10$.
Blue nodes were updated. Red nodes were not updated but they have a pending update.

Now we get another update . This corresponds to . We can update the root node, and add to the children. But the children already have a pending update of . To resolve this, we will compose the functions, i.e. we'll find a single function which is equal to successively applying and then .

combining updates in a segment tree
Segment tree after update $l=0, r=6, g(x) = 3x$.
Blue nodes were updated. Red nodes were not updated but they have a pending update.

More generally, .

Node update function family

In the above example for lazy propagation, is a 'function family'. It represents the set of all possible node update functions for MINMAX.

For any segment tree problem, you'll have to come up with a function family for node update functions. Additionally, this function family will need to be closed under function composition. This means that if and are members of this family, then should also be a member of this family.

This family should also include the identity function. The identity function is the function . In the above example for lazy propagation, is the identity.

(In fact, the function family forms a monoid over function composition, since function composition is always associative.)

Representing the family

To represent a node update function family, we'll need to specify:

  • Function representation: We must be able to represent every function in the family uniquely. In the above example, can be represented by the ordered pair .

  • Function definition: For every function in the family, we must know how to apply it to the input. In the above example, is the definition.

  • The identity function: The function . In the above example, is the identity function. It should also be possible to check whether a function is the identity function.

  • Function composition: A rule for how to compose 2 functions. In the above example, the composition of and is .

C++ example

When we write a generic segment tree library in C++, we can make the node update function family a template parameter.

Here's an example of how to represent node update functions as a class for the MINMAX problem:

class LinearUpdFunc {
public:
    int a, b;  // function representation

    MinMaxElem operator()(const MinMaxElem& x) const {
        // function definition
        return MinMaxElem(x.x_min * a + b, x.x_max * a + b);
    }

    LinearUpdFunc():
        // identity function
        a(1), b(0) {}

    bool is_identity() const {
        return (a == 1) && (b == 0);
    }

    LinearUpdFunc(const LinearUpdFunc& l, const LinearUpdFunc& r):
        // function composition
        a(l.a * r.a), b(l.a * r.b + l.b) {}
};

In the segment tree library, we can call the above methods on the templated function family type without needing to know what they do.

Generic segment tree implementation

We will use 2 arrays: values and pending. values[i] is the value of the node of the segment tree. pending[i] is the pending node update function of the node. Initially, values is constructed from the input array and pending[i] is the identity function for every node .

You can see my C++ segment tree library for an example of how to write generic segment trees.

Bringing problems to standard form

To use the generic segment tree implementation, we should be able to come up with a suitable query monoid and a suitable node update function family. Let's look at some examples:

SUMREPL:

  • , where is an array of size . Therefore, identity is , and .
  • For the update function , the node update function is . The identity function is , which cannot be expressed as for any . Function composition: and .

CHAROCC:

  • Each node of the segment tree stores the frequency of every lowercase English letter. Identity element is an array with all zeros. Creating a leaf node from a string involves computing frequencies of each character. The binary operator is defined as element-wise addition of the arrays.
  • A node update function is represented as an array of length 26. Applying the function involves elementwise addition of to a segment tree node value. Functions are composed by adding their arrays element-wise. The identity function has all elements 0. The update function with character corresponds to an array where the entry of is 1 and all other entries are 0.

KADANE:

You are given an array of integers, indexed from 0 to . The query function is the largest contiguous subarray sum (i.e., find a contiguous subarray of the input such that the sum of the numbers in the subarray is maximum, and then return that maximum sum). You will be asked to perform operations. Each operation will be one of the following:

  • given integers and , output .
  • given integers , and , replace by for all .

The problem of coming up with a suitable monoid and a suitable node update function family is left as an exercise.

Minor hint

See the proof of correctness of Kadane's algorithm. Use divide-and-conquer instead of an incremental approach.

Major hint

Each segment tree node stores 4 values for its segment:

  1. Sum of the elements of the segment
  2. Largest prefix sum of the segment
  3. Largest suffix sum of the segment
  4. Largest subarray sum of the segment