题目描述
如题，已知一个数列，你需要进行下面两种操作：
将某一个数加上 x
求出某区间每一个数的和
输入格式：
第一行包含两个正整数，分别表示该数列数字的个数和操作的总个数。
第二行包含 n个用空格分隔的整数，其中第 i个数字表示数列第 i项的初始值。
接下来 m行每行包含 3 个整数，表示一个操作，具体如下：
1 x k含义：将第 x 个数加上 k
2 x y含义：输出区间[x,y] 内每个数的和
输出格式：
输出包含若干行整数，即为所有操作 2 {2}2 的结果。
输入输出样例
输入：
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
输出：
14
16
题解
结构体：
#include <bits/stdc++.h> using namespace std; #define ls u<<1 #define rs u<<1|1 typedef long long ll; const int N = 500010; struct node{ int l, r; ll sum; }tr[N << 2]; int a[N]; int n, m; void pushup(int u) { tr[u].sum = tr[ls].sum + tr[rs].sum; } void build(int u, int l, int r) { tr[u] = {l, r}; if(l == r) { tr[u].sum = a[l]; 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 += x; return ; } int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) modify(ls, l, r, x); else 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; if(l <= mid) v = query(ls, l, r); if(r > mid) v += query(rs, l, r); return v; } // https://www.luogu.com.cn/problem/P3374 int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", a + i); build(1, 1, n); while(m--) { int op, x, y; scanf("%d%d%d", &op, &x, &y); if(op == 1) { modify(1, x, x, y); } else { printf("%lld\n", query(1, x, y)); } } return 0; }
数组：
小坑的地方：LL和ll，当然变量名可以自己换
当然，节点维护的左右 L , R 也可以作为参数传进函数中，不必开数组去存。
#include <bits/stdc++.h> using namespace std; #define ls u<<1 #define rs u<<1|1 typedef long long LL; const int N = 500010; LL tr[N << 2], L[N << 2], R[N << 2]; int a[N]; int n, m; void pushup(int u) { tr[u] = tr[ls] + tr[rs]; } void build(int u, int l, int r) { L[u] = l, R[u] = r; if(l == r) { tr[u] = a[l]; 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] += x; return ; } int mid = ll + rr >> 1; if(l <= mid) modify(ls, l, r, x); else 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; if(l <= mid) v = query(ls, l, r); if(r > mid) v += query(rs, l, r); return v; } // https://www.luogu.com.cn/problem/P3374 int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", a + i); build(1, 1, n); while(m--) { int op, x, y; scanf("%d%d%d", &op, &x, &y); if(op == 1) { modify(1, x, x, y); } else { printf("%lld\n", query(1, x, y)); } } return 0; }
