Range Query structures and Group Theory

WIP! Last updated Oct 26 2025 while I am still updating my site

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, but I feel it is not represented as much.

Codeforces blog entry

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;
  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) {}
  BIT(vector<int>& a) : n(a.size()), t(n+1, 0) {
    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). Note the order matters since we never assume this combination is commutative anywhere - it is always about applying a new value to an existing value.

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;
  T z;
  combine C;
  inverse I;

  T queryTo(int i) {
    T res = 0;
    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), z(std::move(z)),
    combine(std::move(C)), inverse(std::move(I)), {}
  BIT(vector<T>& a, T z, combine C, inverse I) : n(a.size()), t(n+1, z) {
    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] = combine(t[i], x);
    }
  }
  void set(int i, T x) {
    T diff = combine(x, inverse(a[i]));
    add(i, diff);
    a[i] = std::move(x);
  }
  int query(int l, int r) {
    return sumTo(r) - sumTo(l-1);
  }
};

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.

Thus, our implementation could handle this by only defining an inversecombine(x, y).

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 z 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.

// TODO

For this problem, segment trees also come to mind. Fundamentally, we can answer a range by strictly combining the result from ranges, but we still need the inverse if we update nodes.

Also, go over Lazy segments with range query - now you need two types for combine and update