Maxi135798642's blog

Range add update and range xor query part 2.
By Maxi135798642, history, 5 months ago, In English

Introduction

This blog is a continuation of part 1. In this post, I will explain an optimization to the SQRT Decomposition part.

Prerequisites

Before reading this post, you should be familiar with:

  • part 1
  • predecessor problem
  • fractional cascading

Recap

We want a data structure that works under $$$Z_{2^i}$$$ and allows us to add value k to a range, and query the number of elements within a specific value range inside a given index range.

SQRT Decomposition

Definitions

First let $$$T_p$$$ be the time complexity of a predecessor data structure we want to use(We need to assume that we use a reasonable structure, not worse than BBST). For example, if we use y-fast trie $$$T_p = \mathcal{O}(\log\log \text{MAX})$$$.

Notice that if we just store a predecessor data structure in each block of a previous SQRT decomposition, we achieve complexity $$$\mathcal{O}(\sqrt{n}\cdot T_p)$$$. This is not ideal. We aim to achieve $$$\mathcal{O}(\sqrt{N\cdot T_p})$$$.

Decomposition

Our decomposition is two-dimensional. First we split an array into blocks of size $$$\sqrt{\frac{N}{T_p}}$$$ and then we group these blocks into groups of size $$$T_p$$$. For each group we store a lazy value.

Each group is maintained as a fractional cascading structure over its blocks. For the first block(the root of the cascading), we store a predecessor data structure.

Count

We iterate over all groups and from a fractional cascading considering the lazy value. Thanks to this we know for all blocks in this group how many elements in the given range are in this group in $$$\mathcal{O}(T_p)$$$. Blocks that are partially inside our query are processed naively. This gives us a complexity of $$$\mathcal{O}(\sqrt{\frac{N}{T_p}}\cdot T_p + \sqrt{\frac{N}{T_p}}) = \mathcal{O}(\sqrt{N\cdot T_p})$$$.

Add

For each group fully inside our query, we update the lazy value.

We have at most 2 border groups (groups partially covered by the query). For each of them, we need to recompute the fractional cascading structure:

  1. Partial Blocks: The specific blocks containing the query boundaries ( l and r) are recalculated naively. We can re-sort them using the predecessor data structure in $$$\mathcal{O}(\text{size}\cdot T_p)$$$.
  2. Full Blocks: The blocks inside the group that are not cut by the query boundaries are easy to sort. Since we are in $$$Z_{2^i}$$$, adding a value results in a cyclic shift, which we can fix in $$$\mathcal{O}(\text{size})$$$.
  3. Merge: Finally, we rebuild the fractional cascading links for the group.

This takes $$$\mathcal{O}(\sqrt{N\cdot T_p})$$$.

Full text and comments »

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

Range add update and range xor query.
By Maxi135798642, 6 months ago, In English

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}})$$$

Open questions

  • Can you optimize the space complexity?
  • Can you prove that it's not possible?

Part 2

There is part two of this blog, that optimizes the SQRT Decomposition. Part 2

Full text and comments »

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

My not impractical solution to 2037E with smaller number of queries.
By Maxi135798642, 8 months ago, In English

The problem E. Kachina's Favorite Binary String is saying that we have a binary sequence $$$s$$$ that we don't know and we can ask queries. In each query we can choose a subarray and ask about the number of subsequences of $$$01$$$ in this subarray. Your task is to determine the string $$$s$$$ or say that it's impossible.

It might be helpful to read an editorial or solve the problem yourself before reading this blog.

First let's solve the problem using $$$\frac{1}{2}\cdot n + \mathcal{O}(\log{n})$$$ queries(it is possible to do a bit better, but it would be helpful later). To do this we would like to know where is the last occurrence of $$$1$$$. Our first query will be the whole string. If the answer is $$$0$$$ we can just print IMPOSSIBLE, else we can binary search on a prefix. If some prefix gives the same result as a whole string, we know that each element not in this prefix must be $$$0$$$. Now we ignore all elements after this $$$1$$$(they are all $$$0$$$s). What we are interested in is the difference of the results of queries for the prefix ending on this $$$1$$$ and the query for the prefix ending just before this $$$1$$$. This difference is equal to the number of $$$0$$$s let's denote it by $$$k$$$. If at some point $$$k = 0$$$, we know the rest of the sequence(it's all $$$1$$$s). If $$$k=1$$$ we can binary search all $$$0$$$s by comparing the difference of the results for prefixes to $$$k\cdot \text{#elements not in the prefix}$$$. If they are equal, the last $$$0$$$ is in the smaller prefix, else it's not. The key upgrade to the editorial solution is an observation that since we know the number of zeros, we can ask queries not about each prefix but just every two prefixes. We can present the results in the following table.

characters in s difference
00 0
01 k
10 k-1
11 2k

Now it's clear why we want to binary search for $$$k=1$$$($$$k-1 = 0$$$ and we cannot differentiate between $$$10$$$ and $$$00$$$).

So now how to solve the problem using $$$\frac{1}{3}\cdot n + \mathcal{O}(\log{n})$$$. We start asking about every three prefixes. And we get the following table:

characters in s difference
000 0
001 k
010 k-1
011 2k
100 k-2
101 2k-1
110 2k-2
111 3k

The only problem being that for this we need $$$k\geq3$$$, so for $$$k=2$$$ we can't use it. Fortunately I've described the binary search part in such a way that it can be used for $$$k=2$$$. Seeing this you might think "Why can't we do more, like $$$\frac{1}{100}\cdot n+\mathcal{O}(\log{n})$$$, since the binary search part can be used for any constant $$$k$$$?". The problem is that for both $$$0110$$$ and $$$1001$$$ we have the same difference($$$2k-2$$$). So how could we achieve something better?

Interestingly enough we will achieve $$$\frac{1}{4}\cdot n + \mathcal{O}(\log{n})$$$, but as $$$\frac{1+4}{20}\cdot n + \mathcal{O}(\log{n})$$$. The idea is that for large enough $$$k$$$ you can differentiate between all the different differences from the table. For not large enough $$$k$$$($$$k \leq 100$$$) we just use binary search. The problem being that you can't differentiate between the sequences that have the same difference. To solve this we will ask four range queries depending on the results of the previous ones. The claim is that this works(you always can ask such $$$4$$$ queries to determine the sequence) for asking about every twenty prefixes and those four additional queries inside this substring. You can write a simple program to see that this is the case.

Sadly asking $$$5$$$ additional queries is hard to check brute force like.

My code that checks 4 additional queries

Open questions: Can we get better constant than $$$\frac{1}{4}$$$? Maybe with some faster checker we can check the case with 5 additional queries in a reasonable time?

Full text and comments »

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