RSumQLazyPropSegTree.cpp

// coder : adist98
// dynamic RangeSumQuery using segment trees and lazy propagation//
#include<bits/stdc++.h>

using namespace std;

void updateSegTreelazy(long long int segTree[], long long int lazy[], long long int startRange, long long int endRange, long long int delta, long long int low, long long int high, long long int pos){

	if(low > high){
		return;
	}

	if(lazy[pos] != 0){
		segTree[pos] += lazy[pos]*(high-low+1);
		// check for leaf nodes
		if(low != high){
			lazy[2*pos + 1] += lazy[pos];
			lazy[2*pos + 2] += lazy[pos];
		}
		lazy[pos] = 0;
	}

	// no overlap condition
	if(startRange > high || endRange < low){
		return;
	}

	// total overlap condition
	if(startRange <= low && endRange >= high){
		segTree[pos] += delta*(high-low+1);
		long long int mid = (low+high)/2;
		if(low != high){
			//long long int mid = (low+high)/2;
			lazy[2*pos + 1] += delta;
			lazy[2*pos + 2] += delta;
		}
		return;
	}

	// case of partial overlap
	long long int mid = (low+high)/2;
	updateSegTreelazy(segTree, lazy, startRange, endRange, delta, low, mid, 2*pos+1);
	updateSegTreelazy(segTree, lazy, startRange, endRange, delta, mid+1, high, 2*pos+2);
	segTree[pos] = segTree[2*pos+1] + segTree[2*pos+2];
}

long long int rangeSumQueryLazy(long long int segTree[],long long int lazy[],long long int qlow,long long int qhigh,long long int low,long long int high,long long int pos){

	if(low > high){
		return 0;
	}

	if(lazy[pos] != 0){
		segTree[pos] += lazy[pos]*(high-low+1);
		// check for leaf nodes
		if(low != high){
			lazy[2*pos + 1] += lazy[pos];
			lazy[2*pos + 2] += lazy[pos];
		}
		lazy[pos] = 0;
	}
	// no overlap
	if(qlow > high || qhigh < low){
		return 0;
	}

	// total overlap
	if(qlow <= low && qhigh >= high){
		return segTree[pos];
	}

	// partial overlap
	long long int mid = (low+high)/2;
	return (rangeSumQueryLazy(segTree, lazy, qlow, qhigh, low, mid, 2*pos+1) + rangeSumQueryLazy(segTree, lazy, qlow, qhigh, mid+1, high, 2*pos+2));

}

void ConstructTree(long long int input[], long long int segTree[],long long int low,long long int high,long long int pos){
    if(low == high){
        segTree[pos] = input[low];
        return;
    }
    int mid = (low+high)/2;
    ConstructTree(input, segTree, low, mid, 2*pos + 1);
    ConstructTree(input, segTree, mid+1, high, 2*pos + 2);
    segTree[pos] = segTree[2*pos+1] + segTree[2*pos+2];
}

long long int rangeSumQuery(long long int segTree[],long long int qlow,long long int qhigh,long long int low,long long int high,long long int pos){
    // case of total overlap
    if(qlow <= low && qhigh >= high){
        return segTree[pos];
    }
    // case of no overlap
    if(qlow > high || qhigh < low){
        return 0;
    }
    // case of partial overlap
    long long int mid = (low+high)/2;
    return (rangeSumQuery(segTree, qlow, qhigh, low, mid, 2*pos+1) + rangeSumQuery(segTree, qlow, qhigh, mid+1, high, 2*pos+2));
}
int main()
{
    long long int n = 8;
    long long int a[n] = {0,0,0,0,0,0,0,0};
    long long int segTree[4*n + 1] = {0};
    long long int lazy[4*n + 1] = {0};
    //ConstructTree(a, segTree, 0, n-1, 0);
    //i have now constructed a segment tree
    // i will now give some queries
    updateSegTreelazy(segTree, lazy, 1,3,26,0,7,0);
    updateSegTreelazy(segTree, lazy, 3,7,80,0,7,0);
    updateSegTreelazy(segTree, lazy, 3,6,20,0,7,0);
    cout << rangeSumQueryLazy(segTree, lazy, 7,7,0,7,0);
}