P3374 【模板】树状数组 1和2（洛谷） 谁借莪１个温暖的怀抱￠ 2021-07-16 12:34 275阅读 0赞 [模板1题目][1] Code: #include<iostream> #include<string> #include<memory.h> typedef long long ll; #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) //#define int long long using namespace std; ll a, b, x, y, ans; struct node { ll l, r, w, f; }tree[500005*4]; inline void build(int k, int ll, int rr)//建树 { tree[k].l = ll, tree[k].r = rr; if (tree[k].l == tree[k].r) { cin>>tree[k].w; return; } int m = (ll + rr) / 2; build(k * 2, ll, m); build(k * 2 + 1, m + 1, rr); tree[k].w = tree[k * 2].w + tree[k * 2 + 1].w; } inline void down(int k)//标记下传 { tree[k * 2].f += tree[k].f; tree[k * 2 + 1].f += tree[k].f; tree[k * 2].w += tree[k].f * (tree[k * 2].r - tree[k * 2].l + 1); tree[k * 2 + 1].w += tree[k].f * (tree[k * 2 + 1].r - tree[k * 2 + 1].l + 1); tree[k].f = 0; } inline void ask_interval(int k)//区间查询 { if (tree[k].l >= a && tree[k].r <= b) { ans += tree[k].w; return; } if (tree[k].f) down(k); int m = (tree[k].l + tree[k].r) / 2; if (a <= m) ask_interval(k * 2); if (b > m) ask_interval(k * 2 + 1); } inline void change_point(int k)//单点修改 { if (tree[k].l == tree[k].r) { tree[k].w += y; return; } if (tree[k].f) down(k); int m = (tree[k].l + tree[k].r) / 2; if (x <= m) change_point(k * 2); else change_point(k * 2 + 1); tree[k].w = tree[k * 2].w + tree[k * 2 + 1].w; } int main() { FAST; int n, m; cin >> n >> m; build(1, 1, n); for (int i = 1;i <= m;i++) { int t;cin >> t; if (t == 1) { cin >> x >> y; change_point(1); } else { ans = 0;cin >> a >> b; ask_interval(1); cout << ans << endl; } } } [模板二题目][Link 1] #include<iostream> #include<string> #include<memory.h> typedef long long ll; #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) //#define int long long using namespace std; ll a, b, x, y, ans; struct node { ll l, r, w, f; }tree[5000005]; inline void build(int k, int ll, int rr)//建树 { tree[k].l = ll, tree[k].r = rr; if (tree[k].l == tree[k].r) { cin>>tree[k].w; return; } int m = (ll + rr) / 2; build(k * 2, ll, m); build(k * 2 + 1, m + 1, rr); tree[k].w = tree[k * 2].w + tree[k * 2 + 1].w; } inline void down(int k)//标记下传 { tree[k * 2].f += tree[k].f; tree[k * 2 + 1].f += tree[k].f; tree[k * 2].w += tree[k].f * (tree[k * 2].r - tree[k * 2].l + 1); tree[k * 2 + 1].w += tree[k].f * (tree[k * 2 + 1].r - tree[k * 2 + 1].l + 1); tree[k].f = 0; } inline void ask_point(int k)//单点查询 { if (tree[k].l == tree[k].r) { ans = tree[k].w; return; } if (tree[k].f) down(k); int m = (tree[k].l + tree[k].r) / 2; if (x <= m) ask_point(k * 2); else ask_point(k * 2 + 1); } inline void change_point(int k)//单点修改 { if (tree[k].l == tree[k].r) { tree[k].w += y; return; } if (tree[k].f) down(k); int m = (tree[k].l + tree[k].r) / 2; if (x <= m) change_point(k * 2); else change_point(k * 2 + 1); tree[k].w = tree[k * 2].w + tree[k * 2 + 1].w; } inline void ask_interval(int k)//区间查询 { if (tree[k].l >= a && tree[k].r <= b) { ans += tree[k].w; return; } if (tree[k].f) down(k); int m = (tree[k].l + tree[k].r) / 2; if (a <= m) ask_interval(k * 2); if (b > m) ask_interval(k * 2 + 1); } inline void change_interval(int k)//区间修改 { if (tree[k].l >= a && tree[k].r <= b) { tree[k].w += (tree[k].r - tree[k].l + 1) * y; tree[k].f += y; return; } if (tree[k].f) down(k); int m = (tree[k].l + tree[k].r) / 2; if (a <= m) change_interval(k * 2); if (b > m) change_interval(k * 2 + 1); tree[k].w = tree[k * 2].w + tree[k * 2 + 1].w; } int main() { FAST; int n, m; cin >> n >> m; build(1, 1, n); for (int i = 1;i <= m;i++) { int t;cin >> t; if (t == 1) { cin >> a >> b >> y; change_interval(1); } else { cin >> x; ans = 0; ask_point(1); cout << ans << endl; } } } [1]: https://www.luogu.com.cn/problem/P3374 [Link 1]: https://www.luogu.com.cn/problem/P3368
还没有评论，来说两句吧...