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


2

I am not sure if choosing stacks/heap is related with object oriented programming. The stacks are adopted by many programming languages because they are perfect fit for scoped variables, e.g. create new stack frame at the beginning of a function, and discard it when leaving. They don't always store reference variables, but actual objects. In C++, you can ...


1

Make an augmented search tree. This is an ordinary binary search tree, where each node additionally stores the number of elements in its subtree. This data structure is known as order statistic tree. If we balance the BST (making it an AVL tree for instance) then insertion can, of course, be done in logarithmic time (incrementing the node count along the ...


1

One thing that I haven't seen mentioned is the difference between the space complexities of quicksort and heapsort. An efficient version of quicksort would have O(logn) space, but heapsort is constant O(1) space since no recursion or additional space allocation of any kind is required. That would of course make heapsort more space efficient than merge sort ...


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{...


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