1 Introduction

This is a generalization of the online knapsack problem, which is an generalization of a hard offline knapsack problem used by Quora.

A naive algorithm just recompute the knapsack each time using a dynamic programming algorithm. This would take $O(mnC)$ time, where $m$ is the total number of updates, $n$ is the maximum number of objects in the sequence. The rest of the article describe the idea of decomposable function, which lead to an solution that solves this problem in $O(mC)$ time.

2 Decomposable function

We will use ${▹}_{i=1}^n{x}_i$ to mean $x_1▹\dots ▹x_n▹i{d}_{▹}$, and ${◃}_{i=1}^n{x}_i$ to mean $i{d}_{▹}◃x_1◃\dots ◃x_n$.

$f$ is called decomposable if there exist $(▹,\bowtie ,◃)$ such that it’s decomposable.

The intuition is the function $f$ can be decomposed into solving two pieces of problems. Each piece of the problem has a incremental nature.

$D_C(x_1,\dots ,x_n)$, the maximum value possible given objects $x_1,\dots ,x_n$ and a knapsack of capacity $C$ is a decomposable function. If $x_1▹\dots ▹x_n$ produces the last row of the common dynamic programming algorithm for the knapsack, then we can let $\bowtie$ to be an operation that combine the last rows to output a value.

3 Implement the data structure

Intuitively, $▹$ and $◃$ produces two stacks. $\bowtie$ combines the information on the stack to produce the solution to $f$.

3.1 $◃$, a stack

Say $S=x_1,\dots ,x_n$. We store ${◃}_{i=1}^k{x}_i$ for all $1\le k\le n$, and whenever there is an insertion, we compute ${◃}_{i=1}^{n+1}{x}_i={◃}_{i=1}^n{x}_i◃x_{n+1}$ in one monoid operation. Deletion can be handled by discarding a value. In the worst case, $◃$ gets called only once.

But this requires us to store $O(n)$ values after the fold. We can decrease the extra space to store only $O(\sqrt{n})$ prefix sums.

Let $S(k)={◃}_{i=1}^k{x}_i$. Originally we store $S(k)$ for all $1\le k\le n$. We show how we store only when $k$ is a perfect square and around $\sqrt{n}$ other elements. If $k^2\le n<(k+1{)}^2$, we make sure we store $S(i)$ for all $i$ between $k^2$ and $n$, and do not store any non perfect square $i$ smaller than $(k-1{)}^2$(this means we actively clean them up as $n$ grows large). Assume we are deleting, we can delete around $\sqrt{n}$ elements before we hit a perfect square, in that case we would need to recompute the sums from the previous perfect square. It’s not hard to see some amortized analysis, the extra space can be made into $O(\sqrt{n})$.

Actually, there is a entire range of space/time trade-offs possible. $O(1/ϵ)$ amortized time per operation and $O(n^{ϵ})$ extra space [1].

3.2 $\bowtie$, combine two stacks to simulate a deque

First, let’s consider we are allowed to add on both side of the sequence, but deletion is only at the beginning of the sequence.

The idea is to build this through two stacks. This is a very common problem, and we can see the solutions here. One thing to remember is that the left stack uses $▹$, the right stack uses $◃$.

We can try to simulate the deque with 3 stacks(where $n$ deque operation maps to $9n$ stack operations) [2], but that is just an interesting exercise. We just need to use our two stack set up as in the queue and occasionally rebuild everything. When our front stack become empty and we remove an element in front of our sequence, we just rebuild the structure with two stacks of the same size. There are ways to do the rebuilding without use extra space. The case on the other side is handled symmetrically. Therefore we still maintain $O(1)$ amortized monoid time per operation and $O(\sqrt{n})$ extra space. Finally, we combine the result through $\bowtie$.

4 Examples

I have the code sample for the entire framework along with the examples. There are only $6$ functions.

emptyDecomposableDequeue initialize the data structure with the corresponding functions. pushFront, pushBack, popFront and popBack manipulates the sequences. measure returns the result after apply our decomposable function to the sequence.

4.1 Knapsack

Our common dynamic programming formulation is to sequentially compute tables $D_S$, such that $D_S[C]$ contains the maximum value picking objects from $S$ with knapsack capacity $C$.

Usually, we order the objects as $x_1,\dots ,x_n$, and $S_i=\{x_1,\dots ,x_i\}$. We compute table $D_{S_{i+1}}$ from $D_{S_i}$ in $O(C)$ time. This should be the operation for $▹$ and $◃$. To get the particular entry $D_{S\cup T}[C]$, $O(C)$ time suffice if we are given table for $D_S$ and $D_T$. This would be the $\bowtie$ operation.

This implies if the sequence size is at most $n$, then for any sequence of $m$ operations, we can dynamically compute all $f$ in $O(mC)$ time using only $O(\sqrt{n}C)$ space. Notice once we convert the general algorithm to work in this special case, it is essentially the solution by Lei Huang. In fact, this general data structure is inspired by his solution.

4.2 Maximum subarray sum

The common dynamic programming problem of finding the maximum sum in an array(or, here we consider as a sequence) with both negative and positive numbers. One can compute it in linear time with Kadane’s algorithm. This is a decomposable function, too.

Let ${▹}_{i=j}^k{x}_i=(a,b,c,d)$, where $a$ is the maximum sum using the beginning, $b$ is the sum of all elements from the beginning, $c$ is the maximum using the current element and $d$ is the maximum seen so far. $◃$ is defined similarly. One can see that $(a,b,c,d^{\prime })\bowtie (a^{\prime },b^{\prime },c^{\prime },d^{\prime })=\max (a+a^{\prime },d,d^{\prime })$.

4.3 Dynamic sum of a sequence of elements

A simpler version of this problem is asked in CS theory, where we are allowed to add in one end and delete in another.

Let $f$ be the sum of elements in the sequence, then $f$ is $(+,+,+)$-decomposable. There is a more general statement:

Of course, there is already a data structure support this–a finger tree [3]. Because of the monoid structure, we can even allow concatenations.

References