Fenwick trees for products mod 2ⁿ

After browsing some articles about Fenwick trees (aka Binary Indexed Trees) and seeing remarks such as "let f be some group operation" and "prefix operations such as sum, product, XOR and OR", I started to wonder about the case of combining products (mod 2ⁿ) with range queries. In this case f is not a group operation, unless we restrict ourselves to working with odd values, which are invertible modulo a power of two (this can be done fairly efficiently, see eg Hacker's Delight or a more recent improved algorithm). And neither do we restrict ourselves to computing prefix products, which would have worked without requiring inverses.

Inverses of elements are not strictly required for range queries, and are not used in the usual implementations of a Fenwick tree: while a subtraction can be viewed as (or defined as) adding a negative, that already shows that what we need is an inverse operation, not necessarily an inverse element. Inverse elements are commonly used in the range-update/point-query and range-update/range-update configurations of Fenwick trees, but can be avoided there at the cost of some code duplication. So it would be possible to have a Fenwick tree where f is multiplication in ℤ\{0}, which is not a group operation either, since we can use division instead of multiplication by the reciprocal. Doing that and taking the result mod 2ⁿ would be a possible implementation of "a Fenwick tree for products mod 2ⁿ". As a bonus we could represent zero as 2ⁿ, which maps to zero in the end but doesn't break division. Since the size of the product of two integers is approximately the sum of the sizes of the multiplicands, this would tend to build up large integers of a size comparable to the size (total size, not number of elements) of the entire tree. Not great.

A more reasonable solution would be to convert numbers x (for non-zero x) to the form d*2^k where k = tzcnt(x), tracking the exponents in a normal additive Fenwick tree and the odd integers d in a multiplicative (mod 2ⁿ) Fenwick tree which Just Works^(tm) because odd integers are invertible mod 2ⁿ. Zero can be represented as 2ⁿ again. Point-updates can be statelessly and commutatively undone^[1], as long as you promise not to do it wrong in a way that creates negative exponents.

Something like that is probably what you expected based on the title of the post anyway.

---

I may have waffled a bit more than usual, especially in the second paragraph, but I did it by hand. No LLMs were used to write this post. I accidentally triggered Google AI summaries a couple of times while looking things up though.

[1] For general monoids, you could save a backup of the entries that are modified by a point-update, then undo the update by restoring from the backup - stateful and not commutative. That's a bit annoying, but not quite impossible, as is sometimes suggested.

What is abs(x - y)

What is abs(x - y), why do I even bother asking a question like that, much less answer it? Trust me, it's more interesting than it looks.

To start with, here's something that it is not. Despite appearances, it's not the absolute difference between x and y. If we were working with unlimited integers, sure, but as usual I'm imagining a context in which every integer is implicitly assumed to have some finite size. There are several valid ways to compute the absolute difference between x and y (henceforth absdiff_u(x, y) for the unsigned absolute difference, and absdiff_s(x, y) for the signed absolute difference, which does not return a signed result but rather interprets its inputs as signed integers) but abs(x - y) is not one of them when you're working with fixed-size integers.

Absolute difference

Probably the most obvious way to compute absdiff_γ(x, y) is max_γ(x, y) - min_γ(x, y), where γ is the signedness of choice. You can think about geometrically (in terms of a number line) if you want. There's no "funny business", the subtraction doesn't wrap in the unsigned case and doesn't overflow in the signed case.

Based on the ranges of the functions alone there's an argument to show that abs(x - y) cannot possibly implement absdiff of either signedness: abs(x - y) cannot return a value greater than half the range of its type. Eg no value greater than 0x80000000 when working with 32-bit integers [1]. The distance between two integers can be up to and including the maximum value that can fit in the corresponding unsigned type, almost half of those potential distances cannot be returned by abs(x - y).

By the way an interesting and sometimes useful way to compute absdiff_u(x, y) is subus(x, y) | subus(y, x) where subus is subtraction with unsigned saturation. At least one of subus(x, y) and/or subus(y, x) is zero (if x == y then both are zero, otherwise one of them saturates to zero) so the parts can be ORed or added or XORed to give whichever of them is not zero, or zero if both are zero.

Clockwise distance

Another possible notion of distance between fixed-size integers is their clockwise distance: how far do you have to go in the positive direction around the number ring (the way I drew the ring back then, actually it would be counter-clockwise distance, but let's not dwell on that) to get from x to y. If, having started at x, we reach y before crossing the "boundary" (there is no boundary, but it feels like one) between the highest unsigned integer and zero, then that distance is obviously y - x. Otherwise, it's the distance to the highest unsigned integer, plus one, plus the distance from zero to y:

0xFFFFFFFF - x + 1 + y =
~x + 1 + y =
-x + y =
y - x

So the clockwise distance from x to y is y - x either way, that's nice and simple.

Since we're working around the number ring, there is no difference between a clockwise distance between signed integer and a clockwise distance between unsigned integers. You could even interpret the distance as a signed quantity, reinterpreting very large positive distances into smaller negative distances. [2]

This notion of difference is obviously not commutative, subtraction being famously anti-commutative. We should expect that, because depending on which way around x and y are, the clockwiseness either lets you go the short way between x and y or forces you to go the long way around the ring. For antipodal points on the ring it doesn't make any difference which way around you go, but for most pairs of x and y there is a short way and a long way. That leads into the next notion of distance.

The shortest way around the ring

What if we forget about going clockwise and could go either way around the ring whichever is shorter, we get a commutative notion of distance again. Based on how the clockwise distance was calculated, one way to express the "shortest way around the ring" is min_u(x - y, y - x). The notion of minimum used here should be the unsigned minimum, even if x and y were thought of as signed (which once again doesn't matter around the ring), the signed minimum would pick a large negative distance over a short positive one which is not what we set out to compute.

min_u(x - y, y - x) is equivalent to (... insert drumroll ...) abs(x - y). Let's prove it, why not. I will assume 32-bit integers, that's not fundamental to the proof but it's easier to assume a specific size.

First let's recall that y - x = -(x - y).

• If x - y = 0x80000000 then y - x is also 0x80000000 and we have min_u(0x80000000, 0x80000000) = 0x80000000 = abs(0x80000000).
• If x - y < 0x80000000 (ie non-negative when interpreted as a signed integer) then y - x would be > 0x80000000 (negative when interpreted as a signed integer), x - y < y - x and abs doesn't perform its conditional negation, min_u(x - y, y - x) = x - y = abs(x - y).
• If x - y > 0x80000000 (ie negative when interpreted as a signed integer) then y - x would be < 0x80000000 (non-negative when interpreted as a signed integer), x - y > y - x and abs does perform its conditional negation, min_u(x - y, y - x) = y - x = abs(x - y).

There is nothing inherently wrong with this notion of distance, but likely most uses of abs(x - y) "in the wild" were not written with the intent to compute the "shortest way around the ring" type of distance.

Programming-language Annoyances

One aspect that I've pointedly ignored in the rest of this post is concerns such as trapping on overflow (either in normal arithmetic or in abs), or undefined behaviour, or the difference of unsigned integers yielding a signed integer of a wider type. Such concerns are your responsibility if you use any of the expressions from this post; I mention them primarily to head off pointless discussions.

---

I didn't write this post with AI. You can tell because the writing is dense and awkward as usual.

1. [1] but 0x80000000 is a potential output, so hopefully you are interpreting the result of abs(x - y) as an unsigned integer, or you don't mind the occasional Integer.MIN_VALUE showing up.
2. [2] the math doesn't care about your interpretation, but you might.