Hello recently I attempted this problem: http://codeforces.com/contest/341/problem/D
I understand editorial's solution, but I found in comments a very nice solution, that appears it can be generalized to query sums or higher dimensions. Here is it.
Notice that we could do + and - subtraction interval-wise. But Fenwick tree could only update per range and query per element or vice versa. If, for each element, say, ft(x, y) hold the sum of prefix sum of the matrix (1, 1, x, y) (ie. prefix sum of prefix sum of (x, y)), then for each query, ft(x1, y1) - ft(x0 - 1, y1) - ft(x1, y0 - 1) + ft(x0 - 1, y0 - 1) would be the result. As the difference between prefix-sum is the sum of the corresponding interval. And it's easy to xor a v to elements in submatrix (x0, y0, x1, y1). Consider 1 dimension version of this problem. For a sequence a, the prefix sum of x is and the prefix sum of prefix sum of x is . Hence, all we have to do is to maintain an extra sequnce i * ai. Then expand method above to arbitrary dimension.
Link to code : http://codeforces.com/contest/341/submission/4391987
I could only get a vague idea, but not much into detail of what's going on especially the code. With this being a 4 years old comment, I don't think it's a good idea to ask the guy who posted, but can anyone please clarify in an easier way, or provide similar problems/blogs to it? Perhaps how to solve this problem if it was for sum queries instead of xor using this technique.