Is it possible to implement a range-update range-xor fenwick tree?

Revision en1, by chromate00, 2022-06-22 03:49:23

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English chromate00 2022-06-22 03:49:23 746 Initial revision (published)