Bits, Math and Performance(?): Fenwick trees for products mod 2ⁿ
Friday, 26 June 2026
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*2k 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.
Posted by
Harold
at<br>10:09
Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest
Older Post
Home
Blog Archive
2026
(2)
June
(2)
Fenwick trees for products mod 2ⁿ
What is abs(x - y)
2025
(2)
December
(1)
June
(1)
2024
(10)
December
(1)
November
(1)
August
(1)
June
(3)
May
(1)
April
(1)
March
(1)
January
(1)
2023
(7)
September
(1)
July
(1)
June
(1)
May
(1)
April
(2)
January
(1)
2022
(1)
July
(1)
2021
(2)
July
(1)
June
(1)
2020
(2)
September
(1)
May
(1)
2019
(1)
October
(1)
2018
(2)
August
(2)
2017
(3)
December
(2)
August
(1)
2016
(1)
November
(1)
2014
(1)
April
(1)
2013
(4)
September
(1)
August
(1)
May
(1)
April
(1)
2012
(11)
November
(3)
September
(8)
About Me
Harold
View my complete profile