Прибавление на отрезке
public
Jun 11, 2024
Never
65
1 #include <bits/stdc++.h> 2 #define ll long long 3 #define f first 4 #define s second 5 6 using namespace std; 7 8 const int inf = 1e9 + 3; 9 10 vector<ll> tree; 11 vector<ll> add; 12 vector<int> a; 13 14 void build(int v, int tl, int tr) { 15 if (tl == tr) { 16 tree[v] = a[tl]; 17 add[v] = 0; 18 } else { 19 int tm = (tl + tr) / 2; 20 build(v * 2, tl, tm); 21 build(v * 2 + 1, tm + 1, tr); 22 tree[v] = tree[v * 2] + tree[v * 2 + 1]; 23 add[v] = 0; 24 } 25 } 26 27 void push(int v, int tl, int tr) { 28 if (add[v] != 0) { 29 int tm = (tl + tr) / 2; 30 tree[v * 2] += (tm - tl + 1) * add[v]; 31 add[v * 2] += add[v]; 32 33 tree[v * 2 + 1] += (tr - tm) * add[v]; 34 add[v * 2 + 1] += add[v]; 35 36 add[v] = 0; 37 } 38 } 39 40 void update(int v, int tl, int tr, int l, int r, ll x) { 41 if (r < tl || tr < l) { 42 return; 43 } 44 if (l <= tl && tr <= r) { 45 tree[v] += (tr - tl + 1) * x; 46 add[v] += x; 47 return; 48 } 49 int tm = (tl + tr) / 2; 50 push(v, tl, tr); 51 update(v * 2, tl, tm, l, r, x); 52 update(v * 2 + 1, tm + 1, tr, l, r, x); 53 tree[v] = tree[v * 2] + tree[v * 2 + 1]; 54 } 55 56 ll sum(int v, int tl, int tr, int l, int r) { 57 if (r < tl || tr < l) { 58 return 0; 59 } 60 61 if (l <= tl && tr <= r) { 62 return tree[v]; 63 } 64 65 push(v, tl, tr); 66 int tm = (tl + tr) / 2; 67 ll s1 = sum(v * 2, tl, tm, l, r); 68 ll s2 = sum(v * 2 + 1, tm + 1, tr, l, r); 69 70 return s1 + s2; 71 } 72 73 int main() { 74 int n, m; 75 cin >> n >> m; 76 a.resize(n + 1); 77 tree.resize(4 * n); 78 add.resize(4 * n); 79 for (int i = 1; i <= n; ++i) { 80 cin >> a[i]; 81 } 82 build(1, 1, n); 83 84 for (int i = 0; i < m; ++i) { 85 int op, l, r; 86 cin >> op >> l >> r; 87 if (op == 1) { 88 int x; 89 cin >> x; 90 update(1, 1, n, l, r, x); 91 } else { 92 cout << sum(1, 1, n, l, r) << endl; 93 } 94 } 95 96 return 0; 97 }