Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int main() {
- // int n; cin >> n;
- // vector<int> v(n);
- // for (int i = 0; i < n; i++) cin >> v[i];
- // vector<int> ex(n);
- // ex = v;
- // sort(ex.begin(), ex.end());
- // int ans = 0;
- // for (int i = 0; i < n; i++) {
- // if (v[i] != ex[i]) ans++;
- // }
- // cout << ans << endl;
- // //time complexity-> O(n) + O(nlogn) + O(n)--> O(nlogn)
- // //space complexiy-> O(n)
- // int n; cin >> n;
- // vector<int> v(n), hash(101, 0);
- // for (int i = 0; i < n; i++) {
- // cin >> v[i];
- // hash[v[i]]++;
- // }
- // int j = 0, ans = 0;
- // for (int i = 1; i <= 100; i++) {
- // int ele = i, freq = hash[i];
- // while (freq) {
- // if (v[j] != ele) ans++;
- // j++; freq--;
- // }
- // }
- // cout << ans << endl;
- // //time complexity-> O(n);
- // //space complexity-> O(n);
- // int n; cin >> n;
- // vector<int> v(n);
- // for (int i = 0; i < n; i++) cin >> v[i];
- // int q; cin >> q;
- // for (int i = 1; i <= q; i++) {
- // //user input;//0 indexing input
- // int l, r; cin >> l >> r;
- // //cout the sum of ele in range [l,r];
- // //traversing the range;
- // int tempsum = 0;
- // for (int j = l; j <= r; j++) tempsum += v[j];
- // cout << tempsum << endl;
- // }
- // //time -> O(q*n)-> O(n^2);
- int n; cin >> n;
- // vector<int> v(n + 1); // 1 indexing main array
- vector<int> pre(n + 1, 0); // 1 indexing prefix array
- for (int i = 1; i <= n; i++) {
- // cin >> v[i];
- int curr; cin >> curr;
- pre[i] = pre[i - 1] + curr;
- }
- // for (int i = 1; i <= n; i++) {
- // pre[i] = pre[i - 1] + v[i];
- // }
- int q; cin >> q;
- for (int i = 1; i <= q; i++) {
- int l, r; cin >> l >> r;
- cout << pre[r] - pre[l - 1] << endl;
- }
- //time complexity->O(n);
- //space complexity-> O(n);
- /*
- 6
- 4 3 1 3 4 2
- 3
- 2 4--->7
- 1 5--->15
- 3 6--->10
- */
- //main array-> 1 indexing, prefix-> 0 indexing
- //main array-> 0 indexing, prefix -> 0 indexing
- //main array-> 0 indexing, prefix -> 1 indexing
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement