class SegTree { public: SegTree *lchild, *rchild; int leftmost, rightmost; int sum; int lazy=0; SegTree(int leftmost, int rightmost, vector<int>& v) { this->leftmost = leftmost; this->rightmost = rightmost; if(leftmost==rightmost)//at leaf { sum = v[leftmost]; return; } int mid = (leftmost+rightmost)/2; lchild = new SegTree(leftmost, mid, v); rchild = new SegTree(mid+1, rightmost, v); recalc(); } void recalc() //recalculates sum for the segment { if(leftmost==rightmost) return ; sum = lchild->sum + rchild->sum; } void pointUpdate(int index, int val) { updateLazy(); if(leftmost==rightmost){ sum+=val; return; } int mid = (leftmost+rightmost)/2; if(index<=mid) lchild->pointUpdate(index, val); else rchild->pointUpdate(index, val); recalc(); } bool leaf() { return leftmost==rightmost; } void updateLazy() { if(this->lazy!=0){ this->sum += lazy*(rightmost-leftmost+1); if(!leaf()) { lchild->lazy+= lazy; rchild->lazy+= lazy; } lazy=0; } } void rangeUpdate(int left, int right, int val) { updateLazy(); if(right<leftmost or left> rightmost) return; if(right>=rightmost and leftmost>=left){ sum+= val*(rightmost-leftmost+1); if(!leaf()) { lchild->lazy+= val; rchild->lazy+= val; } return; } lchild->rangeUpdate(left, right, val); rchild->rangeUpdate(left, right, val); recalc(); return; } int rangeSum(int left, int right) { if(right<leftmost or left>rightmost) return 0; updateLazy(); if(right>=rightmost and left<=leftmost) return sum; return lchild->rangeSum(left, right)+rchild->rangeSum(left, right); } };