Range Query structures and Group Theory

Range query structures are some of the more advanced data structures encountered in competitive programming. I won’t rehash the fundamentals here (there are many guides online), and the mathematical, group-theory lens of looking at these structures is not new (see this Codeforces blog entry), but I feel it is not represented as much.

The most basic required operations are range query and point update. Let’s first look through the lens of a Binary-Indexed Tree.

Here is the code for a simple point add, range sum case:

class BIT {
  int n;
  vector<int> t, a;
  int sumTo(int i) {
    int res = 0;
    for(i++; i > 0; i -= i & -i) {
      res += t[i];
    }
    return res;
  }
public:
  BIT(int n) : n(n), t(n+1, 0), a(n, 0) {}
  BIT(vector<int>& a) : n(a.size()), t(n+1, 0), a(a) {
    for(int i = 0; i < n; i++) {
      add(i, a[i]);
    }
  }
  void add(int i, int x) {
    for(++i; i <= n; i += i & -i) {
      t[i] += x;
    }
  }
  void set(int i, int x) {
    int diff = x - a[i];
    add(i, diff);
    a[i] = x;
  }
  int rangeSum(int l, int r) {
    return sumTo(r) - sumTo(l-1);
  }
};

Alright, that works, but what if we wanted to make a more generic version? To leverage abstraction, the most powerful tool in mathematics and software design, we need to analyze fundamental assumptions of the values and operations. Let’s keep multiplication over integers in mind for an alternative possible operation.

In this new case add() would instead multiply the numbers, so this should be a generic combination operation instead. t[i] += x would then be t[i] = combine(t[i], x).

Ok, if we change that, we also need to adjust the range sum. So instead of res += t[i], it would be res = combine(res, t[i]).

But there’s another tricky part - the zero. If we still had res = 0, our rangeProduct would always be zero, so we need to set res and default t to 1 instead. More generally, this needs to be the element e where combine(x, e) = combine(e, x) = x, so that we start from a “blank slate” when no combines are applied yet.

So far, having an operation combine() and a value zero gives us a Monoid. For questions that only require add() and sumTo(), this is sufficient. However, we’re not done.

set() introduces a new operation, though quite subtle. In order to properly update a value, we need to add its difference to the current value. Apparently, we need some notion of a inversecombine(x, y) as well; this is also seen in rangeSum.

Formally, this would be represented as combine(x, inverse(y)), where we now also have an inverse operation; This is a Group. By supplying the combine, inverse, and zero, we can create a generic BIT.

template<typename T, typename Combine, typename Inverse> class BIT {
  int n;
  vector<T> t, a;
  T z;
  Combine C;
  Inverse I;

  T queryTo(int i) {
    T res = z;
    for(i++; i > 0; i -= i & -i) {
      res = C(res, t[i]);
    }
    return res;
  }
public:
  BIT(int n, T z, Combine C, Inverse I)
    : n(n), t(n+1, z), a(n, z), z(z), C(std::move(C)), I(std::move(I)) {}
  BIT(vector<T>& a, T z, Combine C, Inverse I)
    : n(a.size()), t(n+1, z), a(a), z(z), C(std::move(C)), I(std::move(I)) {
    for(int i = 0; i < n; i++) {
      add(i, a[i]);
    }
  }
  void add(int i, T x) {
    for(++i; i <= n; i += i & -i) {
      t[i] = C(t[i], x);
    }
  }
  void set(int i, T x) {
    T diff = C(x, I(a[i]));
    add(i, diff);
    a[i] = std::move(x);
  }
  T query(int l, int r) {
    return C(queryTo(r), I(queryTo(l-1)));
  }
};

One more assumption is hiding in there. Each t[i] holds the combined value of a whole block of positions, and add() folds x into that block without recording where inside the block position i sits. That only gives the right answer if order doesn’t matter, and query() likewise cancels a prefix off the right side of a longer prefix. So the BIT silently needs combine to be commutative: the structure it really wants is an abelian group. Addition, xor, and multiplication all qualify; matrix multiplication and string concatenation do not. We’ll come back to this.

But, that’s not the whole story. Consider supporting multiplications over integers. Then the inverse function would be 1/x, which is not in integer domain, but even otherwise would have floating point values, which we all know are imprecise and finnicky.

Our implementation could handle this by only defining an inversecombine(x, y) instead of a standalone inverse. For products this is just integer division x / y, and it’s exact, since a prefix product is always a multiple of any shorter prefix product (ignoring overflow). In practice, most problems ask for products modulo a prime, and there every nonzero value has a modular inverse, so the group is back for free.

Another edge case would also be multiplying by 0. The multiplication group excludes zero, as it does not have an inverse. But, we can adapt by tracking a separate BIT for zero count over integers and addition. If any query contains a positive zero count, return 0, otherwise return the usual query result, and similarly, update the zero BIT when 0 is involved, and the regular BIT otherwise.

Segment trees: dropping the inverse

For this problem, segment trees also come to mind. A segment tree stores the combined value of each node’s range, so a range query combines O(log n) disjoint nodes, and a point set replaces a leaf and recomputes each ancestor from its two children. Nothing is ever subtracted out; we only ever combine. So a segment tree needs just the Monoid, and that is exactly why it handles min, max, and gcd, none of which have an inverse. The zero workaround from above also disappears, since 0 is now just another value under multiplication.

Here is the generic version, using the bottom-up layout:

template<typename T, typename Combine> class SegTree {
  int n;
  vector<T> t;
  T z;
  Combine C;
public:
  SegTree(vector<T>& a, T z, Combine C)
    : n(a.size()), t(2*n, z), z(z), C(std::move(C)) {
    for(int i = 0; i < n; i++) t[n+i] = a[i];
    for(int i = n-1; i > 0; i--) t[i] = C(t[2*i], t[2*i+1]);
  }
  void set(int i, T x) {
    for(t[i += n] = std::move(x); i > 1; i /= 2) {
      t[i/2] = C(t[i & ~1], t[i | 1]);
    }
  }
  T query(int l, int r) {
    T resl = z, resr = z;
    for(l += n, r += n+1; l < r; l /= 2, r /= 2) {
      if(l & 1) resl = C(resl, t[l++]);
      if(r & 1) resr = C(t[--r], resr);
    }
    return C(resl, resr);
  }
};

Notice that commutativity is gone too. Every node is always built as left child combined with right child, and query() keeps a separate left and right accumulator so the pieces are joined in array order. That’s why segment trees over matrices (linear recurrences, DP transitions) or over “bracket balance” states work, and BITs over them don’t.

The trade is that the BIT gets away with a Group by exploiting prefix differences, which buys a smaller constant and about a fifth of the code. When the operation is an abelian group, use the BIT; when it is only a monoid, or not commutative, the segment tree is the one that works.

Lazy propagation: two monoids

Range update adds a second kind of value: the pending updates themselves. These need their own combine, since two updates waiting on the same node must be stacked into one (add 3 then add 5 is add 8), so updates form a monoid too, with “do nothing” as the identity. They also need to act on stored values in a way that agrees with the value combine: applying an update to a node must give the same result as applying it to both children and combining. In algebra terms, each update has to be a monoid homomorphism, f(x ⊕ y) = f(x) ⊕ f(y), and the update monoid acts on the value monoid through these maps.

Range add over range sum is the classic example, and it’s where this rule bites. “Add x” is not a homomorphism on plain sums: adding x to a range of length k adds k*x to its sum, so the sum alone doesn’t carry enough information to apply the update. The fix is to store what the action needs, and the length rides along in the value:

struct S { long long sum; int len; };
S op(S a, S b) { return {a.sum + b.sum, a.len + b.len}; }
S e() { return {0, 0}; }
using F = long long;
S mapping(F f, S x) { return {x.sum + f * x.len, x.len}; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }

Those names are not an accident. The AtCoder Library’s lazy_segtree is parameterized as lazy_segtree<S, op, e, F, mapping, composition, id>, which is exactly this: a value monoid, an update monoid, and the action between them, with the documented requirement that f(x ⊕ y) = f(x) ⊕ f(y). Range assign over range min, range add over range max, and range affine over range sum all drop into the same template by changing only these functions.

Summary

The static structures fit the same lens. Prefix sums are a BIT with the updates removed, so they want the same group. A sparse table answers a query by overlapping two power-of-two blocks, so it additionally needs combine(x, x) = x, which is why it’s the O(1) structure for min, max, and gcd but never for sum.

The nice part of this lens is that the code doesn’t change between problems, only the handful of functions you supply. Figuring out which row a problem lands in is most of the work of picking the structure.