Create a Data Structure which is collection of integers. Create methods to add an element, retrieve an element and addToAll method in O(1) time
# | User | Rating |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Create a Data Structure which is collection of integers. Create methods to add an element, retrieve an element and addToAll method in O(1) time
Name |
---|
You forgot to add "...delete an element, delete all elements, make segment tree faster than bit".
This comment only makes sense if "...add an element" means add an element at any random position.
I just need above three approach can you please explain little bit?
I am sorry you didn't get me. What I meant was it's not possible.
You can use a vector, and an int. You can add numbers to the vector, when you use addToAll, then you add it to the standalone integer, and when retrieving, you get the element from the vector, and add the standalone integer to it. When you add a number, then you have to deduct the integer from it. (-Morass- idea)
The standalone integer can be the 0th element of the vector also, for convenience.
but retriving complexity would not be constant in this case?
You can retrieve from a vector in O(1) and you can add two numbers in O(1). Why wouldn't it be constant?
Thats wrong. After adding 100 to all, I insert a new element. Now I add 1 to all.
According to you, the new element has been incremented by 101, but infact it is incremented by just 1.
Good day to you
imho you can add the element decreased by "100" [the new one] {so you would retrieve "Element-100+101" which is correct}
Have nice day ^_^
Use something like a DSU:
but dsu isn't exactly O(1) :P
It's not hard
Let's start with a plain vector of ints with O(1) amortized insertion at the back
Suppose we have right now N elements and we need to increment them by X, we can keep some separate variable delta indicating how much we added to the whole array without adding said value to each and every element in linear time
Retrieving ith element then is as easy as a[i] + delta
No problem so far as long as we don't insert more elements, because if we were to insert a number V at ith position, a[i] + delta would return a different value V + delta instead of just V, we can get around it by inserting V - delta instead of just V, this way a[i] + delta = (V - delta) + delta = V
It's worth mentioning that deleting an element won't be a problem, just make sure to choose a suitable underlying structure instead of plain vector if necessary to achieve required complexity
To support insertion at arbitrary positions, you may consider a tree-like structure at the cost of increased insertion complexity O(log2(n))
"methods to add an element, retrieve an element" is about as ambiguous as possible. And what even is addToAll?