LazyPropagation.cpp

/**
*
*			Arif Hosan
*American International University Bangladesh
*
**/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#include<cstring>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<sstream>
#include<functional>
#include<stack>
#include<set>
#define PI 2*acos(0.0)
#define SIZE 1000000
#define endl '\n'
int caseno = 1;
#define CP() printf("Case %d:\n",caseno++)
#define R() freopen("in.txt","r",stdin)
#define W() freopen("out.txt","w",stdout)
#define RW R(); W()
#define SFI(_i) scanf("%d",&_i)
#define SFII(_i,_ii) scanf("%d%d",&_i,&_ii)
#define SFD(_i) scanf("%lf",&_i)
#define SFC(_c) scanf("%c",&_c)
#define PFIL(_i) printf("%d\n",_i)
#define PFI(_i) printf("%d",_i)
#define PFSL(_i) printf("%s\n",_i)
#define PFS(_i) printf("%s",_i)
#define NL printf("\n")
#define SPC printf(" ")
#define ALL(_c) _c.begin(),_c.end()
#define ITE(_a,_b) map<_a,_b>::iterator
#define MEM(_c,_v) memset(_c,_v,sizeof(_c))
#define FOR(i,a,b) for(i=(a);i<(b);i++)
#define REV(i,a,b) for(i=(a);i>=(b);i--)
#define valid(nx,ny) nx>=0 && nx<30 && ny>=0 && ny<30
using namespace std;

#define sz 10
int arr[sz], tree[3*sz], lazy[3*sz];

void init(int node, int b, int e) {
	if (b == e) {
		tree[node] = arr[b];
		lazy[node] = 0;
		return;
	}

	int l = node * 2, r = node * 2 + 1, mid = (b + e) / 2;
	init(l, b, mid); init(r, mid + 1, e);
	tree[node] = tree[l] + tree[r];
}

void update(int node, int b, int e, int i, int j,int x) {
	if (i > e || j < b) return;
	if (b >= i && j >= e) {
		tree[node] += (e - b + 1)*x;
		lazy[node] += x;
		return;
	}

	int l = node * 2, r = node * 2 + 1, mid = (b + e) / 2;
	update(l, b, mid, i, j, x); update(r, mid + 1, e, i, j, x);
	tree[node] = tree[l] + tree[r] + lazy[node] * (e - b + 1);
}

int query(int node, int b, int e, int i, int j,int carry) {
	if (i > e || j < b) return 0;
	if (b >= i && j >= e) return tree[node] + carry*(e - b + 1);
	
	int l = node * 2, r = node * 2 + 1, mid = (b + e) / 2;
	
	return query(l, b, mid, i, j, carry + lazy[node]) + query(r, mid + 1, e, i, j, carry + lazy[node]);
}

int main() {
	int i, j;
	int arr2[] = { 0, 4, 1, 2, 3, 9, 8, 7 };
	FOR(i, 0, 8) arr[i] = arr2[i];
	
	init(1, 1, 7);

	FOR(i, 1, 15)	cout << "Node: " << i << " Value: " << tree[i] << endl;

	update(1, 1, 7, 2, 6, 2);

	FOR(i, 1, 15)	cout << "Node: " << i << " Value: " << tree[i] <<" Lazy: "<<lazy[i]<< endl;

	cout << query(1, 1, 7, 2, 2, 0) << endl;
}