chromate00's blog

By chromate00, history, 9 months ago, In English

It is well known that fenwick trees can easily implement Range update/Point query or Point update/Range query on many kinds of operations, and XOR is one of those operations. Also, a range update/range query fenwick tree with sum queries has once been implemented (AFAIK it has been first shown on Petr's blog, correct me if I'm wrong) by treating the range update as updating the first-degree coefficients and the constants separately.

Now I am writing this blog to ask this question: can we expand this idea to operations other than addition, such as XOR(or yet even multiplication)? if it is possible, I would also appreciate an explanation on how it could be implemented.

  • Vote: I like it
  • +11
  • Vote: I do not like it

9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

For range-update & range-xor, I've come up with a solution by maintaining two fenwick tree.

Firstly, knowing that $$$\bigoplus_{i=l}^r a_i=\bigoplus_{i=1}^{l-1}a_i\oplus\bigoplus_{i=1}^r a_i$$$, we only need to answer prefix-xor and perform suffix-update. Let's consider the effect of an update "$$$\forall i\ge p,a_i\leftarrow a_i\oplus x$$$" on a query "$$$\bigoplus_{i=1}^qa_i$$$" ($$$p\le q$$$). Because $$$x\oplus x=0$$$, if $$$2\nmid(q-p)$$$, the answer to such query won't be changed by such update; otherwise, the answer $$$y$$$ will be changed to $$$y\oplus x$$$, just like point-update.

So here comes my solution: use a fenwick tree $$$A$$$ to maintain updates where $$$2\mid p$$$ and queries where $$$2\mid q$$$, and another one $$$B$$$ to maintain updates where $$$2\nmid p$$$ and queries where $$$2\nmid q$$$. Just perform operations like point-update & prefix-query to maintain them. This is a solution in $$$\mathcal O(q\log n)$$$ time.

  • »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow, now this solution is what most people would consider very elegant. I have never thought of using two fenwick trees in such a way.

9 months ago, # |
  Vote: I like it +18 Vote: I do not like it

This comment explains how fenwick trees and segment trees are connected. Turns out that two fenwick trees (one for prefix and one for suffix) store the exact same data as a segment tree. So anything you can do with a segment tree, you can do using two fenwick trees.