Design a data structure

I am trying to design a data structure that stores elements according to some prescribed ordering, each element with its own value, and that supports each 开发者_如何学JAVAof the following four operations in logarithmic time (amortized or worst-case, your choice):

1. add a new element of value v in the kth position
2. delete the kth element
3. returns the sum of the values of elements i through j
4. increase by x the values of elements i through j

Any Idea will be appreciated, Thanks

---

I suspect you could do it with a red-black tree. Over the classic red-black tree, each node would need the following additional fields:

• size
• sum
• increment

The size field would track the total number of child nodes, allowing for log(n) time insertion and deletion.

The sum field would track the sum of its child nodes, allowing for log(n) time summing.

The increment field would be used to track an increment to each of its child nodes which would be added on when calculating sums. So, when calculating the final sum, we would return sum + size*increment. This is the trickiest one. The increment field would be added on when calculating sums. I think by adding positive and negative increments at the appropriate nodes, it would be possible to alter the returned sum correctly in all cases by altering only log(n) nodes.

Needless to say, implementation would be very tricky. Sum and increment fields would have to be updated after each insertion and deletion, and each would have at least five cases to deal with.

Update: I'm not going to try to solve this completely, but I would note that incrementing i through j by n is equivalent to incrementing the whole tree by n, then decrementing 0 through i by n and decrementing j through to the end by n. A global increment can be done in constant time, with the other two operations being a 'left side decrement' and a 'right side decrement', which are symmetrical. Doing a left side decrement to i would be something like, 'take the count of the left subtree of the root node. If it the count is less than i, decrement the increment field on the left child of root by n. Then apply a left decrement of n to to right sub-tree of the root node up to i - count(left subtree) elements. Alternatively, if the count is greater than i, decrement the increment field of the left-left grandchild of the root by n, then apply a left decrement of n to the left-right subtree of the root up to count (left-left subtree) '. As the tree is balanced, I think the left decrement operation need only be recursively applied ln(n) times. The right decrement would be similar, but reversed.

---

What you're asking for isn't feasible.

Requirement #3 might be possible, but #4 just can't be done in logarithmic time. You have to edit at most every node. Imagine i is 0 and j is n-1. You'd have to edit every node. Even with constant access that's linear time.

Edit: Upon further consideration, if you kept track of "mass increases" you could potentially control access to a node, decorating it on the way out with whatever mass increases it required. I still think it would entirely unweildly, but I suppose it's possible.

---

Requirement 1, 2 and 3 can be satisfied by Binary Indexed Tree (BIT, Fenwick Tree): http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

I am thinking of a way to modify BIT to work with #4 in logarithm complexity.