1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107
| #include <iostream> #include <cstdio> using namespace std; typedef long long ll;
ll a[100005]; ll tree[100005]; ll lazy[100005];
namespace st {
void build(int p, int l, int r) { lazy[p] = 0;
if (l == r) { tree[p] = a[l]; return; }
int mid = (l + r) / 2; build(p * 2, l, mid); build(p * 2 + 1, mid + 1, r); tree[p] = tree[p * 2] + tree[p * 2 + 1]; }
void pushdown(int p, int len) { lazy[p * 2] += lazy[p]; lazy[p * 2 + 1] += lazy[p];
tree[p * 2] += (len - len / 2) * lazy[p]; tree[p * 2 + 1] += (len / 2) * lazy[p];
lazy[p] = 0; }
void change(int p, int l, int r, int x, int y, int num) { if (x <= l && y >= r) { lazy[p] += num; tree[p] += (num * ll(r - l + 1)); return; }
pushdown(p, (r - l + 1));
int mid = (l + r) / 2; if (x <= mid) change(p * 2, l, mid, x, y, num); if (y > mid) change(p * 2 + 1, mid + 1, r, x, y, num);
tree[p] = tree[p * 2] + tree[p * 2 + 1]; }
ll find(int p, int l, int r, int x, int y) { if (x <= l && y >= r) return tree[p]; int mid = (l + r) / 2;
if (lazy[p] != 0) pushdown(p, r - l + 1);
ll re = 0;
if (x <= mid) re += find(p * 2, l, mid, x, y); if (y > mid) re += find(p * 2 + 1, mid + 1, r, x, y);
return re; }
}
int main() { int n, m; scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); }
st::build(1, 1, n);
for (int i = 1; i <= m; i++) { int op, x, y, k; scanf("%d", &op); if (op == 1) { scanf("%d %d %d", &x, &y, &k); st::change(1, 1, n, x, y, k); } else if (op == 2) { scanf("%d %d", &x, &y); ll ans = st::find(1, 1, n, x, y); printf("%lld\n", ans); } }
return 0; }
|