「模板」线段树模板

加

void build(int s, int t, int p) {
	if (s == t) {
		d[p] = a[s];
		return;
	}
	int m = (s + t) / 2;
	build(s, m, p * 2);
	build(m + 1, t, p * 2 + 1);
	d[p] = d[p * 2] + d[p * 2 + 1];
}
int getsum(int l, int r, int s, int t, int p) {
	if (l <= s && t <= r) return d[p];
	int m = (s + t) / 2;
	if (b[p] != 0) {
		d[p * 2] += (m - s + 1) * b[p];
		d[p * 2 + 1] += (t - m) * b[p];
		b[p * 2] += b[p];
		b[p * 2 + 1] += b[p];
		b[p] = 0;
	}
	int sum = 0;
	if (l <= m) sum += getsum(l, r, s, m, p * 2);
	if (m + 1 <= r) sum += getsum(l, r, m + 1, t, p * 2 + 1);
	return sum; 
}
void update(int l, int r, int c, int s, int t, int p) {
	if (l <= s && t <= r) {
		d[p] += (t - s + 1) * c, b[p] += c;
		return;
	}
	int m = (s + t) / 2;
	if (b[p] != 0) {
		d[p * 2] += (m - s + 1) * b[p];
		d[p * 2 + 1] += (t - m) * b[p];
		b[p * 2] += b[p];
		b[p * 2 + 1] += b[p];
		b[p] = 0;
	}
	int sum = 0;
	if (l <= m) update(l, r, c, s, m, p * 2);
	if (r > m) update(l, r, c, m + 1, t, p * 2 + 1);
	d[p] = d[p * 2] + d[p * 2 + 1];
}

加、乘、取模

void build(int s, int t, int p) {
	b2[p] = 1;
	if (s == t) {
		d[p] = a[s];
		return;
	}
	int m = (s + t) / 2;
	build(s, m, p * 2);
	build(m + 1, t, p * 2 + 1);
	d[p] = d[p * 2] + d[p * 2 + 1];
	d[p] %= mod;
}
int getsum(int l, int r, int s, int t, int p) {
	if (l <= s && t <= r) return d[p] = d[p] % mod;
	int m = (s + t) / 2;
	if (b2[p] != 1) {
		d[p * 2] *= b2[p];
		d[p * 2] %= mod;
		d[p * 2 + 1] *= b2[p];
		d[p * 2 + 1] %= mod;
		b2[p * 2] *= b2[p];
		b2[p * 2] %= mod;
		b2[p * 2 + 1] *= b2[p];
		b2[p * 2 + 1] %= mod;
		b1[p * 2] *= b2[p];
		b1[p * 2] %= mod;
		b1[p * 2 + 1] *= b2[p];
		b1[p * 2 + 1] %= mod;
		b2[p] = 1;
	}
	if (b1[p] != 0) {
		d[p * 2] += (m - s + 1) * b1[p];
		d[p * 2] %= mod;
		d[p * 2 + 1] += (t - m) * b1[p];
		d[p * 2 + 1] %= mod;
		b1[p * 2] += b1[p];
		b1[p * 2] %= mod;
		b1[p * 2 + 1] += b1[p];
		b1[p * 2 + 1] %= mod;
		b1[p] = 0;
	}
	int sum = 0;
	if (l <= m) sum += getsum(l, r, s, m, p * 2) % mod;
	if (m + 1 <= r) sum += getsum(l, r, m + 1, t, p * 2 + 1) % mod;
	sum %= mod;
	return sum; 
}
void update_mul(int l, int r, int c, int s, int t, int p) {
	if (l <= s && t <= r) {
		d[p] *= c, b2[p] *= c;
		d[p] %= mod;
		b2[p] %= mod;
		b1[p] *= c;
		b1[p] %= mod;
		return;
	}
	int m = (s + t) / 2;
	if (b2[p] != 1) {
		d[p * 2] *= b2[p];
		d[p * 2] %= mod;
		d[p * 2 + 1] *= b2[p];
		d[p * 2 + 1] %= mod;
		b2[p * 2] *= b2[p];
		b2[p * 2] %= mod;
		b2[p * 2 + 1] *= b2[p];
		b2[p * 2 + 1] %= mod;
		b1[p * 2] *= b2[p];
		b1[p * 2] %= mod;
		b1[p * 2 + 1] *= b2[p];
		b1[p * 2 + 1] %= mod;
		b2[p] = 1;
	}
	if (b1[p] != 0) {
		d[p * 2] += (m - s + 1) * b1[p];
		d[p * 2] %= mod;
		d[p * 2 + 1] += (t - m) * b1[p];
		d[p * 2 + 1] %= mod;
		b1[p * 2] += b1[p];
		b1[p * 2] %= mod;
		b1[p * 2 + 1] += b1[p];
		b1[p * 2 + 1] %= mod;
		b1[p] = 0;
	}
	int sum = 0;
	if (l <= m) update_mul(l, r, c, s, m, p * 2);
	if (r > m) update_mul(l, r, c, m + 1, t, p * 2 + 1);
	d[p] = d[p * 2] + d[p * 2 + 1];
	d[p] %= mod;
}
void update_add(int l, int r, int c, int s, int t, int p) {
	if (l <= s && t <= r) {
		d[p] += (t - s + 1) * c, b1[p] += c;
		d[p] %= mod;
		b1[p] %= mod;
		return;
	}
	int m = (s + t) / 2;
	if (b2[p] != 1) {
		d[p * 2] *= b2[p];
		d[p * 2] %= mod;
		d[p * 2 + 1] *= b2[p];
		d[p * 2 + 1] %= mod;
		b2[p * 2] *= b2[p];
		b2[p * 2] %= mod;
		b2[p * 2 + 1] *= b2[p];
		b2[p * 2 + 1] %= mod;
		b1[p * 2] *= b2[p];
		b1[p * 2] %= mod;
		b1[p * 2 + 1] *= b2[p];
		b1[p * 2 + 1] %= mod;
		b2[p] = 1;
	}
	if (b1[p] != 0) {
		d[p * 2] += (m - s + 1) * b1[p];
		d[p * 2] %= mod;
		d[p * 2 + 1] += (t - m) * b1[p];
		d[p * 2 + 1] %= mod;
		b1[p * 2] += b1[p];
		b1[p * 2] %= mod;
		b1[p * 2 + 1] += b1[p];
		b1[p * 2 + 1] %= mod;
		b1[p] = 0;
	}
	int sum = 0;
	if (l <= m) update_add(l, r, c, s, m, p * 2);
	if (r > m) update_add(l, r, c, m + 1, t, p * 2 + 1);
	d[p] = d[p * 2] + d[p * 2 + 1];
	d[p] %= mod;
}