【模板】线段树（区间加、区间乘、区间查询）

C++版本：

区间加法、查询区间和线段树

#define lson (o<<1)
#define rson (o<<1|1)
ll sumv[maxn << 2], addv[maxn << 2], a[maxn];
void cover(ll o, ll l, ll r, ll v) {
	sumv[o] += (r - l + 1)*v;
	addv[o] += v;
}
void pushup(ll o) { sumv[o] = sumv[lson] + sumv[rson]; return; }
void pushdown(ll o, ll l, ll r) {
	ll mid = (l + r) >> 1;
	cover(lson, l, mid, addv[o]);
	cover(rson, mid + 1, r, addv[o]);
	addv[o] = 0;
}
void build(ll o, ll l, ll r) {
	addv[o] = 0;
	if (l == r) { sumv[o] = a[l]; return; }
	ll mid = (l + r) >> 1;
	build(lson, l, mid); build(rson, mid + 1, r);
	pushup(o);
}
void optadd(ll o, ll l, ll r, ll ql, ll qr, ll v) {
	if (ql <= l && r <= qr) { cover(o, l, r, v); return; }
	ll mid = (l + r) >> 1;
	if (addv[o] != 0)pushdown(o, l, r);
	if (ql <= mid)optadd(lson, l, mid, ql, qr, v);
	if (mid < qr)optadd(rson, mid + 1, r, ql, qr, v);
	pushup(o);
}
ll querysum(ll o, ll l, ll r, ll ql, ll qr) {
	if (ql <= l && r <= qr) { return sumv[o]; }
	ll mid = (l + r) >> 1, ans = 0;
	if (addv[o] != 0)pushdown(o, l, r);
	if (ql <= mid)ans += querysum(lson, l, mid, ql, qr);
	if (mid < qr)ans += querysum(rson, mid + 1, r, ql, qr);
	pushup(o);
	return ans;
}

区间加法、区间乘法、查询区间和线段树

ll sumv[maxn << 2], addv[maxn << 2], addx[maxn << 2], a[maxn];
void cover(ll o, ll l, ll r, ll v, ll x) {
	sumv[o] = sumv[o] * x%P;
	addx[o] = addx[o] * x%P;
	addv[o] = addv[o] * x%P;
	sumv[o] = (sumv[o] + (r - l + 1)*v) % P;
	addv[o] = (addv[o] + v) % P;
}
void pushup(ll o) {
	sumv[o] = (sumv[lson] + sumv[rson]) % P;
	return;
}
void pushdown(ll o, ll l, ll r) {
	ll mid = (l + r) >> 1;
	cover(lson, l, mid, addv[o] % P, addx[o] % P);
	cover(rson, mid + 1, r, addv[o] % P, addx[o] % P);
	addx[o] = 1; addv[o] = 0;
}
void build(ll o, ll l, ll r) {
	addv[o] = 0, addx[o] = 1;
	if (l == r) { sumv[o] = a[l] % P; return; }
	ll mid = (l + r) >> 1;
	build(lson, l, mid); build(rson, mid + 1, r);
	pushup(o);
}
void optadd(ll o, ll l, ll r, ll ql, ll qr, ll v) {
	if (ql <= l && r <= qr) { cover(o, l, r, v%P, 1); return; }
	ll mid = (l + r) >> 1;
	if (addv[o] != 0 || addx[o] != 1)pushdown(o, l, r);
	if (ql <= mid)optadd(lson, l, mid, ql, qr, v);
	if (mid < qr)optadd(rson, mid + 1, r, ql, qr, v);
	pushup(o);
}
void optaddx(ll o, ll l, ll r, ll ql, ll qr, ll v) {
	if (ql <= l && r <= qr) { cover(o, l, r, 0, v%P); return; }
	ll mid = (l + r) >> 1;
	if (addv[o] != 0 || addx[o] != 1)pushdown(o, l, r);
	if (ql <= mid)optaddx(lson, l, mid, ql, qr, v%P);
	if (mid < qr)optaddx(rson, mid + 1, r, ql, qr, v%P);
	pushup(o);
}
ll querysum(ll o, ll l, ll r, ll ql, ll qr) {
	if (ql <= l && r <= qr) { return sumv[o] % P; }
	ll mid = (l + r) >> 1, ans = 0;
	if (addv[o] != 0 || addx[o] != 1)pushdown(o, l, r);
	if (ql <= mid)ans += querysum(lson, l, mid, ql, qr);
	if (mid < qr)ans += querysum(rson, mid + 1, r, ql, qr);
	return ans % P;
}

【模板】线段树（区间加、区间乘、区间查询）

原文：https://www.cnblogs.com/JihuiPeng/p/13662775.html