This is not a useful blog, just something I noticed and thought to write down. It's probably been talked about before as well.
Background: Fenwick Tree
The Fenwick tree is a data structure that is commonly used to perform prefix sum queries and point updates on some array
Unable to parse markup [type=CF_MATHJAX]
. Leaving the issue of updates aside the general idea is that, for each index $$$i$$$, it stores the sum of A over the range $$$(i-f(i), i]$$$ (yes, that's an open-closed interval), whereUnable to parse markup [type=CF_MATHJAX]
returns the least significant bit of $$$i$$$.To compute a prefix sum over
Unable to parse markup [type=CF_MATHJAX]
we start with the intervalUnable to parse markup [type=CF_MATHJAX]
(whereUnable to parse markup [type=CF_MATHJAX]
), then we addUnable to parse markup [type=CF_MATHJAX]
(whereUnable to parse markup [type=CF_MATHJAX]
), and so on until we cover the entire range. Since eachUnable to parse markup [type=CF_MATHJAX]
has one fewer bit thanUnable to parse markup [type=CF_MATHJAX]
, this can only happenUnable to parse markup [type=CF_MATHJAX]
times in the worst case. Therefore any prefix sum query is computed inUnable to parse markup [type=CF_MATHJAX]
worst case running time.int fenwick_tree[MAXN];
int prefix(int i) {
int x = 0;
for (; i > 0; i -= f(i)) x += fenwick_tree[i];
return x;
}
It is also easy to compute any range sum query over a range
Unable to parse markup [type=CF_MATHJAX]
by taking the sum over the prefixUnable to parse markup [type=CF_MATHJAX]
and subtractingUnable to parse markup [type=CF_MATHJAX]
.int range(int l, int r) {
return prefix(r) - prefix(l-1);
}
Generalizing
As presented above, instead of sums, we could compute prefix queries for any associative operation, and we could compute range queries for any associative and commutative operation that has an inverse. The requirement on commutativity can be easily removed at the expense of more memory usage and longer implementation. The requirement of an inverse, however, is inherent to the idea of computing ranges by using two overlapping prefixes but is not really necessary to achieve range queries in some other way.
Range queries without inverse
Given this data structure, there is a simple greedy algorithm for computing range queries over
Unable to parse markup [type=CF_MATHJAX]
:- if
Unable to parse markup [type=CF_MATHJAX]
is contained inUnable to parse markup [type=CF_MATHJAX]
, accumulate that range and then compute $$$[l, r-f(r)]$$$ - otherwise, accumulate
Unable to parse markup [type=CF_MATHJAX]
and then computeUnable to parse markup [type=CF_MATHJAX]
It can be shown that this algorithm runs in $$$O(\log(n)^{2})$$$ in the worst case.
I will not write a proof but the intuition is that $$$f(i - f(i))$$$ is twice
Unable to parse markup [type=CF_MATHJAX]
(or zero). That means that in $$$O(\log n)$$$ steps we will cover any interval. We may overshoot, but by that time we will have covered at least half of the interval already, so this process can only happen $$$O(\log n)$$$ times.The code looks something like this:
int range(int l, int r) {
int x = 0;
while (r-l+1 > 0) {
if (f(r) <= r-l+1) {
x += fenwick_tree[r]; r -= f(r);
} else {
x += A[r]; r -= 1;
}
}
return x;
}
I used the sum operation for clarity, but it also works for any associative operation with an identify element.
int range(int l, int r) {
int x = IDENT;
while (r-l+1 > 0) {
if (f(r) <= r-l+1) {
x = OP(fenwick_tree[r], x); r -= f(r);
} else {
x = OP(A[r], x); r -= 1;
}
}
return x;
}
For instance, we could use it with min operation:
#define IDENT INT_MAX
#define OP min
Conclusion
The Fenwick tree can perform arbitrary range queries on associative operations but if we want to do any kind of updates at all, we will need commutative operations. Also, if we want to perform point-assignment updates -- which is the most common for RMQ among others -- we would need an inverse operation.
It has slow complexity compared to e.g. segment trees, and in practice i tested it to be even slower that the obvious sqrt-decomposition approach.
The only situation where I would use this is if we were forced to use the input array in-place, as the Fenwick tree uses exactly N words of memory and is not that hard to build in-place over an existing array.
Thus I conclude that this is not a useful data structure at all.
