Standard Segment Tree with Lazy Propagation || Clean and Structured code || C++
Intuition\nUse the standard segment tree with lazy propagation.\n\n# Complexity\n- Time complexity: O(nlogn)\n\n- Space complexity: O(n)\n\n# Code\n\nclass Segm
# Intuition\nUse the standard segment tree with lazy propagation.\n\n# Complexity\n- Time complexity: O(nlogn)\n\n- Space complexity: O(n)\n\n# Code\n```\nclass SegmentTree{\n  vector<int> segTree, lazy;\n\npublic:\n  SegmentTree(int n){\n    segTree = vector<int>(4 * n, -1);\n    lazy = vector<int>(4 * n, 0);\n  }\n\n  int merge(int a, int b){\n    return max(a, b);\n  }\n\n  void propogate(int st, int ed, int ind){\n    if(st == ed){\n      lazy[ind] = 0;\n      return;\n    }\n    lazy[2*ind] += lazy[ind];\n    lazy[2*ind+1] += lazy[ind];\n    lazy[ind] = 0;\n  }\n\n  void build(vector<int> &arr, int st, int ed, int ind){\n    if (st == ed){\n      segTree[ind] = arr[st];\n      return;\n    }\n\n    int mid = (st + ed) / 2;\n    int left = 2 * ind, right = 2 * ind + 1;\n    build(arr, st, mid, left);\n    build(arr, mid + 1, ed, right);\n    segTree[ind] = merge(segTree[left],segTree[right]);\n  }\n\n  void update(int st, int ed, int ind, int l, int r, int val){\n    if(lazy[ind] != 0){\n      segTree[ind] += lazy[ind];\n      propogate(st, ed, ind);\n    }\n\n    if(st >= l  && ed <= r){  //complete overlap\n      segTree[ind] += val;\n      lazy[ind] = val;\n      propogate(st, ed, ind);\n      return;\n    }\n\n    if(st > r || ed < l){   //disjoint\n      return;\n    }\n\n    int mid = (st + ed) / 2;\n    int left = 2 * ind, right = 2 * ind + 1;\n\n    update(st, mid, left, l, r, val);\n    update(mid + 1, ed, right, l, r, val);\n\n    segTree[ind] = merge(segTree[left], segTree[right]);\n  }\n\n  int query(int st, int ed, int ind, int l, int r){\n    if(lazy[ind] != 0){\n      segTree[ind] += lazy[ind];\n      propogate(st, ed, ind);\n    }\n\n    if (st >= l && ed <= r)\n      return segTree[ind];\n\n    if (l > ed || r < st)\n      return INT_MIN;\n\n    int mid = (st + ed) / 2;\n    int leftAns = query(st, mid, 2 * ind, l, r);\n    int rightAns = query(mid + 1, ed, 2 * ind + 1, l, r);\n\n    return merge(leftAns, rightAns);\n  }\n};\n\nclass Solution {\npublic:\n  int N = 50005;\n  vector<bool> getResults(vector<vector<int>>& queries) {\n    int q = queries.size();\n    vector<int> arr(N);\n    for(int i = 0; i<N; i++)  arr[i] = i;\n    SegmentTree st(N);\n\n    st.build(arr, 0, N-1, 1);\n    set<int> cont;\n    cont.insert(N-1);\n    vector<bool> ans;\n\n    for(auto &it: queries){\n      if(it[0] == 1){\n        int val = st.query(0, N-1, 1, it[1], it[1]);\n        int pos = *cont.lower_bound(it[1]);\n        st.update(0, N-1, 1, it[1]+1, pos, -1*val);\n        cont.insert(it[1]);\n      }\n      else{\n        int val = st.query(0, N-1, 1, 0, it[1]);\n        if(val >= it[2])\n          ans.push_back(true);\n        else  ans.push_back(false);\n      }\n    }\n\n    return ans;\n  }\n};\n```
['Binary Indexed Tree', 'Segment Tree', 'C++']