CODEWITHSUNDEEP
algorithmdata-structurestree
Obaf
Obaf

Reputation: 15

Which all data structures can I use to satisfy the needs mentioned below?

I want to implement a DS which contains a set if numbers {x0, x1, ... , xn}.

Init(n) - sets a numbers x0 = x1 = ... = xn = 0. O(n) worst case.

Get(i) - returns the value of xi. O(log n) worst case.

Add(d, i, j) - adds to all numbers: xi , ... , xj the value "d" (supposed that i <= j). O(log n) worst case.

I want just an idea how can I implement these DS in the mentioned time complexities. Thank you.

Upvotes: 0

Views: 58

Answers (1)

mcdowella
mcdowella

Reputation: 19601

I would start by building a tree, for example the complete binary tree of depth d, where 2^d >= n >= 2^(d-1) so for 5..8 numbers

       g
   e       f
 a   b   c   d
1 2 3 4 5 6 7 8

Now associate a number with every leaf and every internal node.

To extract a value, add together all the numbers on the path to the leaf - O(log n) time.

To add a value to a range of numbers, work from the top and add that value to nodes whose descendants are all in that range and whose parents have some numbers in that range and some numbers not in that range. E.g. to add to 3..7 add to b, c, and 7. There should be at most O(log n) of such numbers because you shouldn't have to update more than two nodes on each level.

Upvotes: 2

Related Questions