Segment Tree RMQ

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
2.7 kB
4
Indexable
Never
class segmentTree {
public:
  int* tree;
  int* lazyTree;
  int N;
  int size;
  
  void update(int qleft, int qright, int delta) {
    update(qleft, qright, delta, 0, N - 1, 0);
  }
  void update(int qleft, int qright, int delta, int left, int right, int index) {
    if(lazyTree[index] != 0) {
      int change = lazyTree[index];
      tree[index] += lazyTree[index];
      lazyTree[index] = 0;
      if(left != right) {
	lazyTree[2*index + 1] += change;
	lazyTree[2*index + 2] += change;
      }
    }
    if(left >= qleft && right <= qright) {
      tree[index] += delta;
      if(left != right) {
	lazyTree[2*index + 1] += delta;
	lazyTree[2*index + 2] += delta;  
      }
    }
    else if(!(right < qleft || left > qright)) {
      int mid = (left + right)/2;
      update(qleft, qright, delta, left, mid, 2*index + 1);
      update(qleft, qright, delta, mid + 1, right, 2*index + 2);
      tree[index] = min(tree[2*index + 1], tree[2*index + 2]);
    }
  }
  int rmq(int qleft, int qright) {
    return rmq(qleft, qright, 0, N - 1, 0);
  }
  int rmq(int qleft, int qright, int left, int right, int index) {
    if(lazyTree[index] != 0) {
      int change = lazyTree[index];
      tree[index] += lazyTree[index];
      lazyTree[index] = 0;

      if(left != right) {
	lazyTree[2*index + 1] += change;
	lazyTree[2*index + 2] += change;
      }
    }
    if(left >= qleft && right <= qright)
      return tree[index];
    if(right < qleft || left > qright)
      return INT_MAX;
    int mid = (left + right)/2;
    return min(rmq(qleft, qright, left, mid, 2*index + 1),
	       rmq(qleft, qright, mid + 1, right, 2*index + 2));
  }
  void createTree(vector<int>& arr, int left, int right, int index) {
    if(left == right)
      tree[index] = arr[left];
    else {
      int mid = (left + right)/2;
      createTree(arr, left, mid, 2*index + 1);
      createTree(arr, mid + 1, right, 2*index + 2);
      tree[index] = min(tree[2*index + 1], tree[2*index + 2]);
    }
  }
  segmentTree(vector<int>& arr) {
    N = arr.size();
    int start = 2;
    while((start - 1) < 2*N) start *= 2;
    size = start - 1;
    tree = new int[size];
    for(int i = 0; i < size; i++)
      tree[i] = INT_MAX;
    lazyTree = new int[size];
    memset(lazyTree, 0, size*sizeof(int));
    createTree(arr, 0, N - 1, 0);
  }
  segmentTree(int sz) {
    N = sz;
    int start = 2;
    while((start - 1) < 2*N) start *= 2;
    size = start - 1;
    tree = new int[size];
    for(int i = 0; i < size; i++)
      tree[i] = INT_MAX;
    lazyTree = new int[size];
    memset(lazyTree, 0, size*sizeof(int));
  }
};