include <bits/stdc++.h>

using namespace std;

define all(v) ((v).begin()), ((v).end())

define sz(v) ((int)((v).size()))

define clr(v, d) memset(v, d, sizeof(v))

define repi(i, j, n) for(int i=(j);i<(int)(n);++i)

define repd(i, j, n) for(int i=(j);i>=(int)(n);--i)

define repa(v) repi(i, 0, sz(v)) repi(j, 0, sz(v[i]))

define rep(i, v) repi(i, 0, sz(v))

define lp(i, cnt) repi(i, 0, cnt)

define lpi(i, s, cnt) repi(i, s, cnt)

define P(x) cout<<#x<<" = { "<<x<<" }\n"

define pb push_back

define MP make_pair

typedef vector vi; typedef vector vd; typedef vector vvi; typedef vector vvd; typedef vector vs; typedef long long ll; typedef long double ld;

int sum_range1(int S, int E, vector & cum_sum) { if (S == 0) return cum_sum[E];

return cum_sum[E] — cum_sum[S — 1]; }

void zero_based() { vector A = { 2, 1, 4, 5, 3, 7 }; vector S(A.size(), 0);

//pre-processing: Compute cumulative sum array for (int i = 0; i < (int) A.size(); i++) S[i] += (i == 0) ? A[i] : A[i] + S[i — 1];

cout << sum_range1(0, 5, S) << "\n"; cout << sum_range1(1, 5, S) << "\n"; cout << sum_range1(2, 4, S) << "\n"; }

int sum_range2(int S, int E, vector & cum_sum) { return cum_sum[E] — cum_sum[S — 1]; }

void one_based() { vector A = { 0, 2, 1, 4, 5, 3, 7 }; // let A[0] = 0 vector S(A.size(), 0);

//pre-processing: Compute cumulative sum array: Start from 1 for (int i = 1; i < (int) A.size(); i++) S[i] += A[i] + S[i — 1];

// 1-based queries cout << sum_range1(1, 6, S) << "\n"; cout << sum_range1(2, 6, S) << "\n"; cout << sum_range1(3, 5, S) << "\n"; }

// sum((i, j) (k, l)) where (k, l) is the bottom right int sum_range(int i, int j, int k, int l, vector<vector> & S) { return S[k][l] — S[k][j-1] — S[i-1][l] + S[i-1][j-1]; }

void accumSum2D() { // 1-based matrix // Append extra top row and col with zero vector<vector> A = { { 0, 0, 0, 0, 0, 0 }, { 0, 1, 2, 2, 4, 1 }, { 0, 3, 4, 1, 5, 2 }, { 0, 2, 3, 3, 2, 4 }, { 0, 4, 1, 5, 4, 6 }, { 0, 6, 3, 2, 1, 3 }, };

// Accumulate each row
for (int i = 1; i < (int) A.size(); i++)
  for (int j = 1; j < (int) A[0].size(); j++)
    A[i][j] += A[i][j-1];

// Accumulate each col
for (int j = 1; j < (int) A[0].size(); j++)
  for (int i = 1; i < (int) A.size(); i++)
      A[i][j] += A[i-1][j];

// 1, 5, 2
// 3, 2, 4
cout << sum_range(2, 3, 3, 5, A) << "\n";

}

int main() {

accumSum2D();

return 0; }