Cp---dsa/13.cpp at master · Pushpendra100/Cp---dsa · GitHub

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <bits/stdc++.h>
using namespace std;
// Pre-computation using Prefix Sum in 1D/2D arrays


/*
    Given array a of N integers. Given Q queries and in each query given L and R print sum of
    array elements from index L to R(L,R included)

    Constraints
    1 <= N <= 10^5
    1 <= a[i] <= 10^9
    1 <= Q <= 10^5
    1 <= L, R <= N
*/

// const int N = 1e5+10;
// int a[N];

// int main() {

//     int n;
//     cin>>n;
//     // in these cases where l and r are given or constraints are given like 1<=l,
//     // then in these cases use 1 base arrays;
//     for (int i = 1; i <= n; i++)
//     {
//         cin>>a[i];
//     }

//     int q;
//     cin>>q;

//     while(q--){
//         int l,r;
//         cin>>l>>r;
//         long long sum = 0;
//         for (int i = l; i <= r; i++)
//         {
//             sum += a[i];
//         }
//         cout<<sum<<endl;

//     }
//     // we calculate time complexity acc to worst case
//     // O(N) + O(Q*N) = O(N^2) = 10^10 iterations


//     return 0;
// }


// const int N = 1e5+10;
// int a[N];
// declare array prefix sum
// int pf[N];

// int main(){
//     int n;
//     cin >> n;
//     for (int i = 1; i <= n; i++)
//     {
//         cin >> a[i];
//         pf[i] = pf[i-1] + a[i];
//         // here we don't need to handle pf[0] case otherwise we need to do if-else
//         // thus in cases of prefix use 1 base array
//     }

//     int q;
//     cin>>q;
//     while(q--){
//         int l,r;
//         cin>>l>>r;
//         cout<<pf[r] - pf[l-1]<<endl;
//     }
//     // O(N) + O(Q) = O(N) = 10^5
// }


/*
    Given 2d array a of N*N integers. Given Q queries and in each query given a, b, c and d, now print sum of rectangle represented
    by (a, b) as top left point and (c, d) as top bottom right point

    Constraints
    1 <= N <= 10^3
    1 <= a[i][j] <= 10^9
    1 <= Q <= 10^5
    1 <= a, b, c, d <= N
*/
// const int N = 1e3 + 10;
// int arr[N][N];
// int main(){
//     int n;
//     cin>>n;
// // in prefix sum cases where two points are given take 1 base array
//     for (int i = 1; i <= n; i++)
//     {
//         for (int j= 1; j <= n; j++)
//         {
//             cin>> arr[i][j];
//         }

//     }
//     int q;
//     cin>>q;
//     while(q--){
//         int a, b, c, d;
//         cin>>a>>b>>c>>d;
//         long long sum = 0;
//         for (int i = a; i <= c; i++)
//         {
//             for(int j = b; j<= d; j++){
//                 sum += arr[i][j];
//             }
//         }
//         cout<<sum<<endl;

//     }
//     // O(N^2) + O(Q*N^2) = 10^5 * 10^6 = 10^11 iterations

// }


const int N = 1e3+10;
int arr[N][N];
long long pf[N][N];

int main(){
    int n;
    cin>>n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin>>arr[i][j];
            pf[i][j] = arr[i][j] + pf[i-1][j] + pf[i][j-1] - pf[i-1][j-1];
        }
    }
    int q;
    cin>>q;
    while(q--){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        cout<<pf[c][d] - pf[a-1][d] - pf[c][b-1] + pf[a-1][b-1]<<endl;
    }
    // O(N^2) + O(Q) = 10^6 + 10^5 = 10^6
}