wish_me's blog

data structure to set all values in O(1)
By wish_me, history, 7 years ago, In English

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

  • Vote: I like it
  • -21
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I just need above three approach can you please explain little bit?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am sorry you didn't get me. What I meant was it's not possible.

      → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but retriving complexity would not be constant in this case?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can retrieve from a vector in O(1) and you can add two numbers in O(1). Why wouldn't it be constant?

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      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 ^_^

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Use something like a DSU:

vector<int> nxt,add,num; //next undefined
int get_add(int pos){
    if(pos>=num.size())return 0;
    add[pos]+=get_add(nxt[pos]);
    if(nxt[pos]<num.size())nxt[pos]=nxt[nxt[pos]];
    return add[pos];
}
void add_element(int x){
    num.push_back(x);
    add.push_back(0);
    nxt.push_back(num.size());
}
int retrieve(int pos){
    return get_add(pos)+num[pos];
}
void add_to_all(int num){
    add[nxt.size()-1]+=num;
}
→ Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

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)) 

struct SomeDataStructure {
  int delta = 0;
  vector<int> a;

  void add(int x) {
    a.emplace_back(x-delta);
  }

  void addToAll(int x) {
    delta += x;
  }

  void get(int i) {
    return a[i] + delta;
  }
}
→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"methods to add an element, retrieve an element" is about as ambiguous as possible. And what even is addToAll?

→ Reply