Блог пользователя wish_me

Автор wish_me, история, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • -21
  • Проголосовать: не нравится

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

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.

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    but retriving complexity would not be constant in this case?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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;
}
»
7 лет назад, # |
Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится

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;
  }
}
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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