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.
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.
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.
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.
I am not aware of the Fenwick tree, can we implement range xor update,range assign update and range sum query on the binary array with segment tree?
You can use one segment tree for each bit, so $$$log(max)$$$ segment trees in total. Now the problem becomes, given an array of $$$0$$$ and $$$1$$$, do range xor update and range sum query. This simple to do.
If the lazy value is $$$0$$$, you do nothing.
If the lazy value is $$$1$$$, you do $$$sum = (r-l+1) - sum$$$, given that the node in the segment tree you are applying it has a value of $$$sum$$$ and covers the range $$$[l,r]$$$.
You can solve the problem in CF: 242E - XOR on Segment