B.contest1.cpp

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

#define MAXN (1 << 17)

long long tsum[2 * MAXN];
long long tupdate[2 * MAXN];

long long query(int x, int A, int B, int a, int b, long long v) {
  if (b <= A || B <= a) {
    /* Query interval and node interval are disjoint. */
    return 0;
  }

  if (a <= A && B <= b) {
    /* Query interval contains the node interval.  Update the node sum and add
     * v to the range update counter. */
    tupdate[x] += v;
    tsum[x] += v * (B - A);
    return tsum[x];
  }

  int M = (A + B) / 2;
  if (tupdate[x]) {
    /* Push range updates down the tree lazily prior to querying. */
    tupdate[2 * x] += tupdate[x];
    tsum[2 * x] += (M - A) * tupdate[x];
    tupdate[2 * x + 1] += tupdate[x];
    tsum[2 * x + 1] += (B - M) * tupdate[x];
    tupdate[x] = 0;
  }

  /* Recursively query each half of the range. */
  long long result = query(2 * x, A, M, a, b, v) +
                     query(2 * x + 1, M, B, a, b, v);
  tsum[x] = tsum[2 * x] + tsum[2 * x + 1];
  return result;
}

int main() {
  int N, M;
  cin >> N >> M;

  for (int i = 0; i < N; i++) {
    /* Read in the leaf node values. */
    cin >> tsum[MAXN + i];
  }
  for (int i = MAXN - 1; i; i--) {
    /* Propogate the sums up the tree. */
    tsum[i] = tsum[2 * i] + tsum[2 * i + 1];
  }

  for (int i = 0; i < M; i++) {
    int c; cin >> c;
    int x, y; cin >> x >> y;
    if (c == 1) {
      cout << query(1, 0, MAXN, x - 1, y, 0) << '\n';
    } else {
      long long v; cin >> v;
      query(1, 0, MAXN, x - 1, y, v);
    }
  }

  return 0;
}