BIT does not support insert operator, but Skip list does. I realized that we can transform a Skip list into a BIT.

Example source code for impatient people:

http://paste.ubuntu.com/8119698/

My data-structure contains some operators:

• Insert x v: insert an element valued v into position x:

For instance: {10,20,30} -> insert 40 3 -> {10,20,40,30}

• Range-sum x y: return sum of elements in ranges x..y

For instance: {10,20,30} -> range-sum 2 3 -> 50

Average complexity of each operator is O(log (max n))

1. Property

a. Parent — child relationship

A is parent of B if A is the first node on the right of B and A is not shorter than B (A is higher or at least equal B height).

b. Sum and Count

In each node, we maintain a value Sum and Count.

Assume u has children u1, u2, ...

Sum[u] = Value[u] + Value[u1] + Value[u2] + ...

Count[u] = 1 + Count[u1] + Count[u2] + ...

2. Operators

a. Accessing an element x-th

• For each level (from 19 to 0), we move as far as possible but still not over x-th element (We use value Count in each node to ensure that we not go over x-th element). Additionally, we must keep array Last[] contain id of last element not exceed x-th element (to use this for later operators).

b. Insert an element into position x

• Access (x-1)-th element, Last[] let us know edges between (x-1)-th and x-th element.
• Disconnect short edges (edges which height <= new element's height), maintain Sum and Count of other elements.
• Insert new element, connect some necessary elements in Last[] with the new element, maintain Sum and Count of relevant elements.
• Connect new element with its parent, maintain Sum and Count of relevant elements.

c. Get sum of a range

Realize (Range-sum x y) = (Range-sum 1 y) — (Range-sum 1 x-1), therefore we only need to process (range-sum 1 x).

• Access x-th element
• Get sum of all of elements in Last[], if an element twice or more, we only plus once.

For example, Last[]={0,0,0,2,3,3,3} -> Answer = Sum[0] + Sum[2] + Sum[3]

3. Example source code

http://paste.ubuntu.com/8119698/

• I tested it and it worked correctly.
• It run fast, complexity of each query is about 2.5 * log (max n)