线段树~懒惰数组的运用

#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 100007
int sum[maxn << 2] = { 0 }, add[maxn << 2];
int a[maxn] = { 0 }, n;
void pushup(int rt)
{
	sum[rt] = sum[rt * 2] + sum[rt * 2 + 1];
}
void build(int l, int r, int rt)
{
	if (l == r)
	{
		sum[rt] = a[l];
		return;
	}
	int m = (l + r) / 2;
	build(l, m, rt * 2);
	build(m + 1, r, rt * 2 + 1);
	pushup(rt);
}
void dxg(int a, int c, int l, int r, int rt)
{
	if (l == r)
	{
		sum[rt] += c;
		return;
	}
	int m = (l + r) / 2;
	if (a <= m)
	{
		dxg(a, c, l, m, rt * 2);
	}
	else
	{
		dxg(a, c, m + 1, r, rt * 2 + 1);
	}
	pushup(rt);
}
void pd(int rt, int ln, int rn)//下推函数,ln,rn,分别为左子树右子树的数字数量
{
	if (add[rt]!=0)
	{
		add[rt * 2] += add[rt];
		add[rt * 2 + 1] += add[rt];
	}
	sum[rt * 2] += add[rt] * ln;
	sum[rt * 2 + 1] += add[rt] * rn;
	add[rt] = 0;
}
void ad(int rt, int c)
{
	add[rt] += c;
}
void qjxg(int L,int R,int c,int l,int r,int rt)
{
	if (L <= l&&r <= R)
	{
		sum[rt] += c*(r - l + 1);//更新数字和，想上表示正确
		add[rt] += c;//更新add标记，表是本区间的sum正确，子区间的add值仍需要调整；
	//	cout << l << " " << r << add[rt]<<" "<<rt << endl;
		return;
	}
	int m = (l + r) / 2;
	pd(rt, m - l + 1, r - m);
	if (L <= m)
	{
		qjxg(L, R, c, l, m, rt * 2);
	}
	if (R > m)
	{
		qjxg(L, R, c, m + 1, r, rt * 2 + 1);
	}
	pushup(rt);
}

int qjcx(int L, int R, int l, int r, int rt)
{
	if (L <= l&&R >= r)
	{
		return sum[rt];
	}
	int m = (r + l) / 2;
	pd(rt, m - l + 1, r - m);
	int ans = 0;
	if (L <= m)
	{
		ans += qjcx(L, R, l, m, rt * 2);
	}
	if (R > m)
	{
		ans += qjcx(L, R, m+1, r, rt * 2 + 1);
	}
	return ans;
}
void p()
{
	for (int s = 1; s <= 20; s++)
	{
		cout << sum[s] << " ";
	}
	cout << endl;
}
int main()
{
	for (int s = 1; s <= 10; s++)
	{
		a[s] = s;
	}
	build(1, 10, 1);
	p();
	dxg(1, 2, 1, 10, 1);
	p();
	cout << qjcx(1, 5, 1, 10, 1) << endl;
	p();
	qjxg(1, 2, -1, 1, 10, 1);
	cout << qjcx(1, 10, 1, 10, 1) << endl;
	p();
	return 0;
}