4

Augment the tree to store, for each subtree, the minimum of the prefix sums of the sequence of elements in that subtree. Then you can check the supergood condition in $O(\log n)$ time. It's your exercise, so I'll let you work out the details. Hint #1: every prefix can be decomposed into a union of $O(\log n)$ subtrees. Hint #2: the minimum of the prefix-...


3

It is not possible to guarantee to find the maximal value that is less than a queried value $V$ in $o(K)$ time with preprocessing in $o(N)$ time. This can be seen easily in the following extreme case. Let $A$ be any array of $N$ integers, which is composed of the following $K=N-1$ linear subarrays. the subarray $A[0], A[1]$ with $C=A[1]-A[0]$. the subarray ...


2

It is on the right direction to try some kind of tree augmented with a global counter that stores the number of all unordered pairs of nodes $\{u,v\}$ such that $v.value+u.value \le d$. The kind of tree you are looking for is a balanced (binary) search tree. Being balanced such as an AVL tree, it supports insertion, deletion and lookup of a number with $O(\...


2

The number of octrees with $n$ nodes is OEIS sequence A007556: $$T(n) = {8n \choose n}/(7n+1)$$ I worked this out, incidentally, by writing a short program to generate the first few values of $T(n)$ and then searching for it. If you had no other information than $n$, then the minimum number of bits required to store an octree with $n$ nodes is $\log\,T(n)$...


1

I share your perception of the problem. The literature on B trees (and it's variants) are written by people who already understand the problem and as such they easily gloss over some details. This does make it difficult to understand. The case of the B+ tree delete operation is somewhat absurd because in contrast with the insert operation (which is ...


1

Could you please explain exactly where you were stuck? Anyway, I'll choose some parts of the solution which were not described by author and shed light on them. You can assume that $T=\sqrt{n}$ in the solution. The main idea can be formulated as follows: For any positive integers $m, n$ such that $m \le n$ either $m \le \sqrt{n}$ or $\frac{n}{m} < \sqrt{...


1

Yes and yes. Any key that doesn't mess up the sort order can be used. Typically (in my experience), this is the minimum value from the right subtree. However, I'm not aware of any specific scenario where this would cause a problem either way. When you delete a key (one practice I have seen is that) you delete the key along with the value. So, if you delete ...


Only top voted, non community-wiki answers of a minimum length are eligible