8
$\begingroup$

The prefix parity problem can be defined as follows. You are given a string $S$ of length $n$ and initially every character is $0$. Then you want to build a data structure that can support updates such as follows.

  1. For a given $i$ change $S[i]$ to either $0$ or $1$
  2. for a given $i$ find the parity of $S[1]+S[2]+...+S[i]$.

From the top of my head, there is a solution that can support these type of queries in $O(\log n)$ time, while only using linear space and linear preprocessing time to build the data structure. The idea is to build a complete binary search tree on top of the string where the leafs correspond to individual characters of $S$ and in every internal node we store the sum of all the characters that are leafs in the sub tree defined by that node. In this way we can trivially support both of the updates in $O(\log n)$ time.

However, I found a paper proving a lower bound for this problem, stating that you can not do better than $O(\frac{\log n}{\log \log n})$ for the updates, and I also found the following paper http://link.springer.com/chapter/10.1007%2F3-540-51542-9_5, and a direct link to the pdf, giving an algorithm achieving that bound, thus being optimal.

I would like to understand this algorithm however the explanation is like 1 page, and a lot of details are missing.

So I was wondering if there is any other source on this problem, because I find it very hard to find any, or is this is the only source available?

thank you in advance

$\endgroup$
9
+100
$\begingroup$

I did a quick read over the paper you linked. Based on the ideas given in that paper, here's a simple data structure that obtains an $O(\frac{\log n}{\log\log n})$ time bound on each operation.

You mentioned in your question that you can use balanced, augmented trees to speed this up. In particular, if you have a binary tree and augment each node with the parity of its left subtree, then you can do updates and lookups in time $O(\log n)$ each. That's fast, but not fast enough.

Now, consider the following generalization of your idea. Suppose that instead of using a binary tree, we use a multiway tree with branching factor $k$. We augment each key in each node with the parity of the all the subtrees preceding it (this generalizes the idea of storing the parity of the left subtree). Now, let's think about how we'd do a lookup or update in this tree. To do a lookup, we use a slightly modified version of the binary tree lookup algorithm from before: walk from the top of the tree down to the bottom, at each step accumulating the parity of the subtree purely to the left of each node. The height of the tree in this case will be $O(\log_k n)$ and we do $O(1)$ work per node, so the cost of doing a lookup will be $O(\log_k n)$.

However, with this setup, the cost of doing an update increases. In particular, if we change the parity of an element, we need to walk up from the bottom of the tree to the top, changing the stored parity of every key in every node on the path upward. There are $k$ keys per node and $O(\log_k n)$ nodes on the path upward from the leaves, so the cost of performing an operation like this will be $O(k \log_k n) = O(\frac{k}{\log k} \log n)$, which is too slow. If we could somehow eliminate this extra $k$ term, then we'd be in business.

The insight the paper has is the following. If you think about our initial problem, we had an array of size $n$ and wanted to be able to compute prefix parities. We now have a $k$-ary tree where, at each node, we need to be able to solve the prefix parity problem on arrays of size $k$ each, since each node caches information about the layers below it. In the above data structure, we solved the prefix parity problem at each node by just storing an array of the prefix parities, which means that if we need to perform an update, the cost is $O(k)$. The paper's insight is that by using a more clever data structure at each node, you can perform these updates significantly more efficiently.

In particular, the paper makes the following insight. Let's suppose that $k$ is "small," for some definition of small that we'll pick later. If you want to solve the prefix parity problem on an array of size $k$, then there are only $2^k$ different possible bit arrays of length $k$. Additionally, there are only $k$ possible lookup queries you could make on a bit array of size $k$. As a result, the number of possible combinations of an array and a query is $k 2^k$. If we pick $k$ to be small enough, we can make this quantity so small that it becomes feasible to precompute the result of every possible array and every possible query. If we do that, then we can update our data structure as follows. In each node of the $k$-way tree, rather than having each key store the parity of its left subtree, we instead store an array of $k$ bits, one for each key in the node. When we want to find the parity of all the nodes to the left of the $i$th child, we just do a lookup in a table indexed by those $k$ bits (treated as an integer) and the index $i$. Provided we can compute this table fast enough, this means that doing a prefix parity query will still take time $O(\log_k n)$, but now updates take time $O(\log_k n)$ as well because the cost of a prefix parity query on a given node will be $O(1)$.

The authors of the paper noticed that if you pick $k = \frac{\lg n}{2}$, then the number of possible queries that can be made is $\frac{\lg n}{2} 2^{\frac{\lg n}{2}} = \frac{\lg n}{2} \sqrt{n} = o(n)$. Additionally, the cost of performing any operation on the resulting tree will be $O(\log_k n) = O(\frac{\log n}{\log \frac{\lg n}{2}}) = O(\frac{\log n}{\log \log n})$. The catch is that you now need to do $o(n)$ precomputation at the start of setting up the data structure. The authors give a way to amortize this cost away by using a different data structure for the initial queries until enough work has been done to justify performing the work necessary to set up the table, though you could argue that you need to spend $O(n)$ time building up the tree in the first place and that this won't affect the overall runtime.

So, in summary, the idea is the following:

  • Instead of using an augmented binary tree, use an augmented $k$-ary tree.
  • Notice that with small $k$, all possible $k$-bit lists and queries on those lists can be precomputed.
  • Use this precomputed data structure at each node in the tree.
  • Choose $k = \frac{\lg n}{2}$ to make the tree height, and, therefore, the cost per operations, $O(\frac{\log n}{\log \log n})$.
  • Avoid the upfront precomputation cost by using a temporary replacement data structure in each node until the precomputation becomes worthwhile.

All in all, it's a clever data structure. Thanks for asking this question and linking it - I learned a lot in the process!

As an addendum, many of the techniques that went into this data structure are common strategies for speeding up seemingly optimal solutions. The idea of precomputing all possible queries on objects of a small size is often called the Method of Four Russians and can be seen in other data structures like the Fischer-Heun data structure for range minimum queries or the decremental algorithm for tree connectivity. Similarly, the technique of using augmented balanced multiway trees with a logarithmic branching factor comes up in other contexts, like the original deterministic data structure for dynamic graph connectivity, where such an approach is used to speed up connectivity queries from $O(\log n)$ to $O(\frac{\log n}{\log \log n})$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.