What is a possible data structure $X$ which stores non-negative integers $x_1, x_2, ..., x_n$ which supports the following operations:

  • $index(k, X)$ returns the biggest $i$ so that $\sum_{i=1}^n x_i \leq k$
  • $sum(j, X)$ returns $\sum_{i=1}^j x_i$

The data structure should support every operation in $O(1)$ (worst case) and use minimum bits as possible.

All that under the assumption : $\sum_{i=1}^{n} x_i= 4n.$

  • $\begingroup$ Getting $sum$ to work should be as simple as caching the sum and adding to it each time you insert while subtracting from it each time you remove elements. Getting $index$ to work could probably work with a 1-dimensional version of a voxel array. Getting it to work in constant time is possible if you uniformly subdivide the voxel array each time you add to it, such that each voxel only has one element in it. $\endgroup$ – michaelsnowden May 14 '16 at 17:39
  • $\begingroup$ @michaelsnowden I don't think there's supposed to be an $add$ / $remove$ operator. It would violate the assumption. Maybe OP should clarify when/how (at initialisation ?) the values are added to the datastructure. $\endgroup$ – Auberon May 14 '16 at 17:42
  • $\begingroup$ @Auberon Indeed. We need some clarification on how the structure is initialized and some clarification on if and how the data structure is modified. $\endgroup$ – michaelsnowden May 14 '16 at 17:45
  • $\begingroup$ It's not clear what you are asking for. 1. What do you mean by "every operation"? Besides index and sum, does it have to support other operations, like insert and delete? Or is this a static data structure that never changes? 2. When you say "minimum bits as possible", do you care about constant factors? 3. What have you tried? What's the best solution you've found so far? What approaches have you considered, and why have you rejected them? $\endgroup$ – D.W. May 14 '16 at 21:35

Browse other questions tagged or ask your own question.