题目描述
如题，已知一个数列，你需要进行下面两种操作：
将某区间每一个数加上 k 。
求出某区间每一个数的和。
输入格式：
第一行包含两个整数 n , m，分别表示该数列数字的个数和操作的总个数。
第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。
接下来 m 行每行包含 3或 4 个整数，表示一个操作，具体如下：
1 x y k：将区间 [ x , y ] 内每个数加上 k 。
2 x y：输出区间 [ x , y ] 内每个数的和。
输出格式：
输出包含若干行整数，即为所有操作 2 的结果。
输入输出样例：
输入：
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
输出：
11
8
20
题解
结构体：
#include <bits/stdc++.h> using namespace std; #define ls u<<1 #define rs u<<1|1 typedef long long ll; const int N = 100010; struct node{ int l, r; ll sum, add; }tr[N << 2]; ll a[N]; int n, m; void pushup(int u) { tr[u].sum = tr[ls].sum + tr[rs].sum; } int len(int u) { return tr[u].r - tr[u].l + 1; } void pushdown(int u) { if(tr[u].add) { tr[ls].sum += tr[u].add * len(ls); tr[rs].sum += tr[u].add * len(rs); tr[ls].add += tr[u].add; tr[rs].add += tr[u].add; tr[u].add = 0; } } void build(int u, int l, int r) { tr[u] = {l, r, 0, 0}; if(l == r) { tr[u].sum = a[l]; tr[u].add = 0; return ;} int mid = l + r >> 1; build(ls, l, mid), build(rs, mid + 1, r); pushup(u); } void modify(int u, int l, int r, int x) { if (tr[u].l >= l && tr[u].r <= r) { tr[u].sum += len(u) * x; tr[u].add += x; return ; } pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) modify(ls, l, r, x); if(r > mid) modify(rs, l, r, x); pushup(u); } ll query(int u, int l, int r) { if(tr[u].l >= l && tr[u].r <= r) { return tr[u].sum; } int mid = tr[u].l + tr[u].r >> 1; ll v = 0; pushdown(u); if(l <= mid) v = query(ls, l, r); if(r > mid) v += query(rs, l, r); return v; } // https://www.luogu.com.cn/problem/P3372 int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%lld", a + i); build(1, 1, n); while(m--) { int op, x, y, k; scanf("%d%d%d", &op, &x, &y); if(op == 1) { scanf("%d", &k); modify(1, x, y, k); } else { printf("%lld\n", query(1, x, y)); } } return 0; }
数组：
#include <bits/stdc++.h> using namespace std; #define ls u<<1 #define rs u<<1|1 typedef long long LL; const int N = 100010; LL tr[N << 2], add[N << 2], L[N << 2], R[N << 2]; LL a[N]; int n, m; void pushup(int u) { tr[u] = tr[ls] + tr[rs]; } int len(int u) { return R[u] - L[u] + 1; } void pushdown(int u) { if(add[u]) { tr[ls] += add[u] * len(ls), add[ls] += add[u]; tr[rs] += add[u] * len(rs), add[rs] += add[u]; add[u] = 0; } } void build(int u, int l, int r) { L[u] = l, R[u] = r; if(l == r) { tr[u] = a[l]; add[u] = 0; return ;} int mid = l + r >> 1; build(ls, l, mid), build(rs, mid + 1, r); pushup(u); } void modify(int u, int l, int r, int x) { int ll = L[u], rr = R[u]; if (ll >= l && rr <= r) { tr[u] += len(u) * x; add[u] += x; return ; } pushdown(u); int mid = ll + rr >> 1; if(l <= mid) modify(ls, l, r, x); if(r > mid) modify(rs, l, r, x); pushup(u); } LL query(int u, int l, int r) { int ll = L[u], rr = R[u]; if(ll >= l && rr <= r) { return tr[u]; } int mid = ll + rr >> 1; LL v = 0; pushdown(u); if(l <= mid) v = query(ls, l, r); if(r > mid) v += query(rs, l, r); return v; } // https://www.luogu.com.cn/problem/P3372 int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%lld", a + i); build(1, 1, n); while(m--) { int op, x, y, k; scanf("%d%d%d", &op, &x, &y); if(op == 1) { scanf("%d", &k); modify(1, x, y, k); } else { printf("%lld\n", query(1, x, y)); } } return 0; }
