C++实现线段树(lazy-tag方法)-区间修改，区间查询

代码如下：

#include <iostream>
using namespace std;
const int N = 10010;
typedef long long LL;
LL input[N];

struct node {
	int l, r;
	LL sum;
	LL add;
} tree[4 * N];

void build(int l, int r, int u) {
	tree[u].l = l;
	tree[u].r = r;
	if (l == r) {
		tree[u].sum = input[l];
		return ;
	}
	int mid = (l + r) >> 1;
	build(l, mid, 2 * u);
	build(mid + 1, r, 2 * u + 1);
	tree[u].sum = tree[2 * u].sum + tree[2 * u + 1].sum;
}

void spread(int u) {
	if (tree[u].add) //当lazy tag不为0时，说明当前区间已经被这个影响所作用，
		//这个区间的所有子区间全都攒着工作没有修改
	{
		tree[2 * u].add += tree[u].add;
		tree[2 * u + 1].add += tree[u].add;
		tree[2 * u].sum += tree[u].add * (tree[2 * u].r - tree[2 * u].l + 1);
		tree[2 * u + 1].sum += tree[u].add * (tree[2 * u + 1].r - tree[2 * u + 1].l + 1);
		tree[u].add = 0;
	}
}

void update(int cl, int cr, int w, int u) {
	if (tree[u].l >= cl && tree[u].r <= cr) {
		tree[u].sum += (LL)w * (tree[u].r - tree[u].l + 1);
		tree[u].add += (LL)w;
		return ;
	}
	spread(u);
	int mid = (tree[u].l + tree[u].r) >> 1;
	if (cl <= mid)
		update(cl, cr, w, 2 * u);
	if (cr > mid)//不能写成(cr >= mid)，不然可能会死循环
		update(cl, cr, w, 2 * u + 1);
	tree[u].sum = tree[2 * u].sum + tree[2 * u + 1].sum;
}

LL query(int cl, int cr, int u) {
	if (tree[u].l >= cl && tree[u].r <= cr)
		return tree[u].sum;
	spread(u);
	int mid = (tree[u].l + tree[u].r) >> 1;
	LL ans = 0;
	if (cl <= mid)
		ans += query(cl, cr, 2 * u);
	if (cr > mid)
		ans += query(cl, cr, 2 * u + 1);
//	cout << ans << endl;
	return ans;
}


int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> input[i];
	build(1, n, 1);
	cout << query(3, 6, 1) << endl;//查询区间[3,6]所有元素之和
	update(3, 6, 3, 1);//给区间[3,6]所有元素加上3
	cout << query(3, 6, 1) << endl;//再次查询区间[3,6]所有元素之和
	return 0;
}

测试结果：