Lazy_Propagation.code-snippets

{
	"Lazy_Propagation": {
		"prefix": "Lazy_Propagation",
		"body": [
		  "template < typename T = int > struct Lazy_Propagation {",
		  "",
		  "    int size;",
		  "    T DEFUALT;",
		  "    vector < T > operations;",
		  "    ",
		  "    void intial(int n){",
		  "        size = 1;",
		  "        DEFUALT = 0;",
		  "        while(size <= n) size *= 2;",
		  "        operations.assign(2 * size, DEFUALT);",
		  "    }",
		  "",
		  "    Lazy_Propagation(int n){",
		  "        intial(n);",
		  "    }",
		  "",
		  "    T operation(T a, T b){",
		  "        return max(a, b);",
		  "    }",
		  "",
		  "    void build(vector < int >& nums, int idx, int lx, int rx){",
		  "        if(lx >= sz(nums)) return;",
		  "        if(rx == lx) operations[idx] = nums[lx];",
		  "        else {",
		  "            int m = (rx + lx) / 2;",
		  "            build(nums, 2 * idx, lx, m);",
		  "            build(nums, 2 * idx + 1, m + 1, rx);",
		  "            operations[idx] = operation(operations[2 * idx], operations[2 * idx + 1]);",
		  "        }",
		  "    }",
		  "",
		  "    // the vector should be 1-based also the tree is 1-based",
		  "    ",
		  "    void build(vector < int >& nums){",
		  "        build(nums, 1, 1, size);",
		  "    }",
		  "",
		  "    void update(int l, int r, int v, int idx, int lx, int rx){",
		  "        if(lx > r || l > rx) return;",
		  "        if(lx >= l && rx <= r){",
		  "            operations[idx] = operation(operations[idx], v);",
		  "            return;",
		  "        }",
		  "        int m = (lx + rx) / 2;",
		  "        update(l, r, v, 2 * idx, lx, m), update(l, r, v, 2 * idx + 1, m + 1, rx);",
		  "    }",
		  "",
		  "    void update(int l, int r, int v){",
		  "        update(l, r, v, 1, 1, size);",
		  "    }",
		  "",
		  "    T query(int i, int idx, int lx, int rx){",
		  "        if(rx == lx) return operations[idx];",
		  "        else {  ",
		  "            int m = (rx + lx) / 2;",
		  "            if(i <= m) return operation(operations[idx], query(i, 2 * idx, lx, m));",
		  "            else return operation(operations[idx], query(i, 2 * idx + 1, m + 1, rx));",
		  "        }",
		  "    }",
		  "",
		  "    T query(int i){",
		  "        return query(i, 1, 1, size);",
		  "    }",
		  "",
		  "};"
		],
		"description": "Lazy_Propagation"
	}
}