Range add update and range xor query.

Introduction

In this blog, I’ll explain a data structure that allows adding value k to all elements in the given range and querying the xor of all elements in the given range.

complexity

Prerequisites

Before reading this post, you should be familiar with:

Segment Trees with lazy propagation
SQRT Decomposition
Sorting and binary search
Basic properties of xor
(Probably some other easy things I forgot to include)

High-level idea

We will use classic segment tree with lazy propagation where in each node we store xor of all the values in the range of this node, and as lazy we will store what to add to the range of the given node.

Unfortunately, only keeping this doesn't allow us to apply lazy to some node. We need to store additional information.

In each segment tree node we will also need to maintain $$$\log(\text{max})$$$ SQRT decompositions, where the i-th decomposition works over $$$\mathbb{Z}_{2^i}$$$.
Each of these decompositions must support two operations:
1. Range add — add a value to all elements in a subrange.
2. Count — count the number of elements that fall within a certain range of values.

SQRT Decomposition over $$$\mathbb{Z}_{2^i}$$$

We will divide an array into blocks of size $$$\mathcal{O}(\sqrt{n})$$$. Assume each element is in range $$$[0; 2^i)$$$. We keep sorted version of each block. For each block we also keep a lazy tag(value we should add to all elements in this block) for both sorted and unsorted version it's the same. Notice that adding k to such block corresponds to some cyclic shift of the sorted version and set of additions under mod in case of the unsorted one.

Range add

We iterate over blocks in our query for each block that is entirely in our query range we just add k to our lazy tag of this block(and mod this tag mod $$$2^i$$$). For bordering blocks we rebuild them. It takes $$$\mathcal{O}(\frac{n}{\sqrt{n}} + \sqrt{n}\cdot\log{n}) = \mathcal{O}(\sqrt{n}\cdot\log{n})$$$.

Count

We iterate over all blocks. For each block we binary search which cyclic shift is yielded by our lazy tag. Under this cyclic shift via classic binary search we can determine how many elements in this block are in the queried range. It works in $$$\mathcal{O}(\frac{n}{\sqrt{n}}\cdot\log{n}) = \mathcal{O}(\sqrt{n}\cdot\log{n})$$$.

Segment tree

In each node of the segment tree we store $$$\log{\text{max}}$$$ SQRT Decompositions like the one described above, xor of elements below and lazy value. In each node the state of the SQRT Decompositions and xor value are only considering lazy tags in this node or below.

Update

If we want to recurse to both children, we add $$$k$$$ on a given range for all SQRT Decompositions and after recursing to both children we recalculate xor as a xor of both children. If we are outside of our query range we just end recursion. If node range is fully in query range we apply adding k to this node and end recursion.

Query

We simply recurse like in normal tree and compute xor.

Apply add k

First imagine that we instead of storing one number — xor of all elements, we store frequency map for each bit(how many elements have 1 on the given bit). Now we have a problem of editing this frequency map based on k.

Naming convention:
$$$k_b$$$ — b'th bit of k(starting from 0).
$$$c$$$ — number of elements that overflow onto b'th bit.
$$$c_0$$$ — number of elements that overflow onto b'th bit and have 0 on b'th bit.
$$$c_1$$$ — number of elements that overflow onto b'th bit and have 1 on b'th bit.
$$$n$$$ — number of elements in the given node.

Notice that if $$$k_b = 0$$$:
$$$\text{ones}'[b] = \text{ones}[b] + c_0 - c_1$$$
else if $$$k_b = 1$$$:
$$$\text{ones}'[b] = n - (\text{ones}[b] + c_0 - c_1)$$$

Assume that you are not in the leaf(if you are the applying is trivial). Under this assumption $$$n$$$ is even and $$$-x \equiv_2 x$$$, so it does not matter if $$$k_b$$$ is $$$0$$$ or $$$1$$$. In both cases $$$\text{ones}'[b] \equiv_2 \text{ones}[b] + c_0 - c_1 \equiv_2 \text{ones}[b] + c_0 + c_1 \equiv_2 \text{ones}[b] + c$$$ (you are only interested in parity of $$$\text{ones}[b]$$$). This tells us that after applying addition of k we just need to flip bit in xor if onto the given bit overflows odd number of elements.

Notice that value $$$v$$$ will overflow onto b'th bit if and only if $$$(v \mod 2^b) + (k \mod 2^b) \geq 2^b$$$. This is equivalent to $$$(v \mod 2^b) \geq (2^b - (k \mod 2^b))$$$. We can ask our b'th SQRT Decomposition to compute for us number of such values $$$v$$$.

After asking about all bits $$$b$$$ and updating xor accordingly, we just update all SQRT Decompositions in this node(add k to the range $$$[0;n)$$$).

Time complexity

Both update and query have the same time complexity. Notice also that at each level of a segment tree we visit constant number of nodes, so the complexity is:

$$$ \mathcal{O}(\log{\text{max}} \cdot (\sqrt{n}\cdot\log{n} + \sqrt{\frac{n}{2}}\cdot\log{\frac{n}{2}} + \sqrt{\frac{n}{4}}\cdot\log{\frac{n}{4}} + ...) ) = \mathcal{O}(\sqrt{n}\log{n}\log{\text{max}})$$$