Suppose you have an array $a$ of $n$ elements in an set $X$, and a associative binary operation $\circ \ \colon X \times X \rightarrow X$, that can be evaluated in constant time, but is costly (e.g. $X$ is the set of $k \times k$ matrices over a finite field $\mathbb{F}_p$, where $k$ is a constant and $p$ is a prime number. Thus multiplying the matrices needs heavy operations such as multiplications and moduli). Say you need to do loads of point updates ($a_i \leftarrow x$) and range queries ($a_l \circ a_{l + 1} \circ \ldots \circ a_r$), and you want to minimizes the number of $\circ$ calls.
It is already known that the segment tree can do just that, doing updates and answering queries both in $O(logn)$ time. It also makes at most $\sim log_2(n)$ calls doing updates and $\sim 2log_2(n)$ calls answering queries.
Additionally, in this paper, it also described how to do the same thing with two Binary Indexed Trees (also known as Fenwick Trees), and achieves significantly better performance on the $min$ operator. I have not tested whether this came from the fact that the bitwise operations gives a faster indexing traversal, or it makes less calls on the $min$ operator.
So, I want to propose a question: What data structure minimizes the number of calls on the combine operator $\circ$? By minimizing, I mean asymptotically optimal, and among those, one that has the smallest leading constant.
To expand the idea further to amortized analysis: given a sequence of $q$ (mixed) queries of those two types, minimize the total number of $\circ$ calls made (in the worst case), as $q \rightarrow \infty$ (taking the constant factor into account, of course).
This question is a copy of my question in cstheory.stackexchange.com. I am looking forward to seeing answers from both sites, and when one answer is correct, I will close the other.
