CODEWITHSUNDEEP
algorithmdata-structureslanguage-agnostic
Jason L
Jason L

Reputation: 520

Looking for a data structure to perform range element update efficiently

I currently have the following data structure:

class DataStructure {
public:
  DataStructure(int n) : m_data(n, 0) {
  }

  void update(int i, int j, int value) {
    for (int k = i; k <= j; ++k) {
      m_data[k] = max(m_data[k], value);
    }
  }

  void reset(int i) {
    m_data[i] = 0;
  }

  int query(int i) {
    return m_data[i];
  }

private:
  vector<int> m_data;
};

So what it does is rather simple:

I need to perform n updates, n resets and n query operations. Currently this code takes O(n*n) time, due to the update operation being O(n) in general.

I am wondering if there are some smart ways to improve this to O(n*log n) time (or better) for n updates, n resets and n query operations, while maintaining O(n) space complexity?

Upvotes: 1

Views: 598

Answers (1)

marvel308
marvel308

Reputation: 10458

Thanks for @qwertman for the explanation here is an algorithm that should work

#include <iostream>
#include <cstdio>
using namespace std;
#define max(a, b) (a>b?a:b)
int tree[100005], lazy[100005];
void init(int idx, int l, int r){
    if(l>r)
        return ;
    if(l==r){
        tree[idx] = 0;
        lazy[idx] = -1;
    }
    else {
        tree[idx] = 0;
        lazy[idx] = -1;
        int mid = (l+r)/2;
        init(2*idx, l, mid);
        init(2*idx+1, mid+1, r);
    }
}
// l and r is for internal use the range a-b has to be updated
void update(int idx, int l, int r, int a, int b, int val, bool isReset){
    if(l>r || b<l || a>r){
        return;
    }
    // printf("idx=%d l=%d r=%d a=%d b=%d val=%d\n",idx,l,r,a,b,val);
    if(lazy[idx] != -1){
        tree[idx] = max(tree[idx], lazy[idx]);
        lazy[2*idx] = max(lazy[2*idx], lazy[idx]);
        lazy[2*idx+1] = max(lazy[2*idx+1], lazy[idx]);
        lazy[idx] = -1;
    }
    if(l>=a && r<=b){
        // printf("updating\n");
        tree[idx] = max(tree[idx], val);
        if(isReset){
            tree[idx] = val;
        }
        lazy[2*idx] = max(lazy[2*idx], val);
        lazy[2*idx+1] = max(lazy[2*idx+1], val);
        lazy[idx] = -1;
    }
    else {
        int mid = (l+r)/2;
        update(2*idx, l, mid, a, b, val, isReset);
        update(2*idx+1, mid+1, r, a, b, val, isReset);
        tree[idx] = max(tree[2*idx], tree[2*idx+1]);
    }
}
int query(int idx, int l, int r, int a){
    if(l>r || a<l || a>r){
        return -1;
    }
    // printf("idx=%d l=%d r=%d a=%d\n",idx,l,r,a);
    if(lazy[idx] != -1){
        tree[idx] = max(tree[idx], lazy[idx]);
        lazy[2*idx] = max(lazy[2*idx], lazy[idx]);
        lazy[2*idx+1] = max(lazy[2*idx+1], lazy[idx]);
        lazy[idx] = -1;
    }
    if(l==a && r==a){
        // printf("----l=%d r=%d a=%d tree=%d\n",l,r,a,tree[idx]);
        return tree[idx];
    }
    else {
        int mid = (l+r)/2;
        int left = query(2*idx, l, mid, a);
        int right = query(2*idx+1, mid+1, r, a);
        return max(left, right);
    }
}
int main() {
    // initializing everything to 0 
    init(1, 1, 10);

    // updating range 1-4 with value 7
    update(1, 1, 10, 1, 4, 7, false);

    // query for 3 should result in 7
    cout << query(1, 1, 10, 3) << endl;

    // updating 3-3 with value 9
    update(1, 1, 10, 3, 3, 9, false);

    // should give 9
    cout << query(1, 1, 10, 3) << endl;

    // isReset is set to true, so the function will do a hard reset
    update(1, 1, 10, 3, 3, 0, true);

    // should give 0
    cout << query(1, 1, 10, 3) << endl;
    return 0;
}

you can run this code at http://ideone.com/Mkp4dQ
some useful links for learning segment tree with lazy propagation
hackerearth Geeksforgeeks

Upvotes: 1

Related Questions