Untitled
unknown
plain_text
2 years ago
1.9 kB
3
Indexable
#include <iostream> using namespace std; const int N = 300010; int tsum[4 * N], tadd[4 * N], a[N]; int n, q; void merge(int v) { tsum[v] = tsum[v * 2] + tsum[v * 2 + 1]; } void build(int v, int tl, int tr) { if (tl == tr) { tsum[v] = a[tl]; tadd[v] = 0; return; } int tm = (tl + tr) / 2; build(v * 2, tl, tm); build(v * 2 + 1, tm + 1, tr); merge(v); } void upd(int v, int val, int tl, int tr) { tadd[v] += val; tsum[v] += (tr - tl + 1) * val; } void push(int v, int tl, int tr) { int tm = (tl + tr) / 2; if (tadd[v] != 0) { /*tadd[v * 2] += tadd[v]; tsum[v * 2] += (tm - tl + 1) * tadd[v]; tadd[v * 2 + 1] += tadd[v]; tsum[v * 2 + 1] += (tr - tm) * tadd[v];*/ upd(v * 2, tadd[v], tl, tm); upd(v * 2 + 1, tadd[v], tm + 1, tr); tadd[v] = 0; } } void update(int v, int tl, int tr, int l, int r, int val) { if (l > r) return; if (l == tl && r == tr) { tsum[v] += (tr - tl + 1) * val; tadd[v] += val; return; } push(v, tl, tr); int tm = (tl + tr) / 2; update(v * 2, tl, tm, l, min(r, tm), val); update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, val); merge(v); } int sum(int v, int tl, int tr, int l, int r) { if (l > r) return 0; if (l == tl && r == tr) return tsum[v]; push(v, tl, tr); int tm = (tl + tr) / 2; return sum(v * 2, tl, tm, l, min(r, tm)) + sum(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r); } int main() { cin >> n >> q; for (int i = 1; i <= n; i++) cin >> a[i]; build(1, 1, n); for (int i = 1; i <= q; i++) { int t, l, r; cin >> t >> l >> r; if (t == 1) { int val; cin >> val; update(1, 1, n, l, r, val); } else cout << sum(1, 1, n, l, r) << "\n"; } return 0; }
Editor is loading...