Data Structure in C++: Prefix Sum Query and Binary Search

Range sum query

Given 2 numbers N and Q, an array A of N number and Q number of pairs L, R. For each query Q print a single line that contains the summation of all numbers from index L to index R.

Input

First line contains two numbers N, Q (1≤N,Q ≤10^5) where N is number of elements in A and Q is number of query pairs.

Second line contains N numbers(1≤ Ai ≤ 10^9).

Next Q lines contains L, R (1≤ L ≤ R ≤ N).

Output

For each query Q print a single line that contains the summation of all numbers from index L to index R.

Examples

Input

6 3
6 4 2 7 2 7
1 3
3 6
1 6

Output

12
18
28

Input

4 3
5 5 2 3
1 3
2 3
1 4

Output

12
7
15

Try on your own first.

Photo by Alvaro Reyes on Unsplash

Solution:

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, q;
    cin >> n >> q;
    vector<long long> a(n);
    vector<long long> pre(n);
    // Reading the array and building the prefix sum array

    cin >> a[0];
    pre[0] = a[0];

    for (int i = 1; i < n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    // Answering the queries
    while (q--) {
        long long l, r;
        cin >> l >> r;
        l--; // Convert to 0-based index
        r--; // Convert to 0-based index

        if (l == 0) {
            cout << pre[r] << endl;
        } else {
            cout << pre[r] - pre[l - 1] << endl;
        }
    }
    return 0;
}

Explanation

Using vector instead of raw arrays:

• vector<long long> a(n); and vector<long long> pre(n); improve memory management and readability.

Combined Reading and Prefix Calculation:

• The prefix sum array pre is built-in while reading the input in a single loop, improving efficiency.

Time Complexity:

• Building the prefix sum array takes O(N) time.
• Each query is answered in O(1) time.
• Thus, the total complexity is O(N + Q), which is optimal for the problem constraints.

Get Prefix Sum

Problem Statement

You will be given an integer array A of size N. You need to print the prefix sum array of the array A in reverse order.

Input Format

• First line will contain N.
• Next line contains the array A.

Constraints

1. 1 <= N <= 1⁰⁵
2. 1 <= A[i] <= 1⁰⁹; Where 0 <= i < N

Output Format

• Output the prefix sum array in reverse order.

Sample Input 0

5
2 4 1 5 3

Sample Output 0

15 12 7 6 2

Explanation 0

The prefix sum of the given array is: 2 6 7 12 15.
The reverse order is: 15 12 7 6 2.

Sample Input 1

3
1000000000 1000000000 1000000000

Sample Output 1

3000000000 2000000000 1000000000

Try to solve it on your own.

Photo by Pankaj Patel on Unsplash

Solution:

#include<bits/stdc++.h>
using namespace std;
int main (){
    long long int n;
    cin>>n;
    vector<long long int>v(n);
    for(long long int i=0; i<n; i++){
        cin>>v[i];
    }
    long long int pre[n];
    pre[0]=v[0];
    for(long long int i=1;i<n;i++){
        pre[i]=v[i]+pre[i-1];
    }
    for(long long int i=n-1; i>=0; i--){
        cout<<pre[i]<<" ";
    }
    return 0;
}

Binary Search

Given 2 numbers N and Q, array A of N numbers and Q queries each one contains a number X.

For each query print a single line that contains “found” if the number X exists in array A otherwise, print “not found”.

Input

First line contains two numbers N, Q (1≤ N,Q ≤10^5).

Second line contains N numbers (1≤ Ai≤ 10^9).

Next Q lines contains X (1≤ X≤ 10^9).

Output

Print the answer for each query in a single line.

Example

Input

5 3
1 5 4 3 2
5
3
6

Output

found
found
not found

Try on your own.

Canva AI-generated picture.

Answer:

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // Sort the array to apply binary search
    sort(a.begin(), a.end());

    while (q--) {
        int x;
        cin >> x;
        bool flag = false;

        int l = 0;
        int r = n - 1;

        while (l <= r) {
            int mid = l + (r - l) / 2;

            if (a[mid] == x) {
                flag = true;
                break;
            }

            if (a[mid] < x) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        if (flag) {
            cout << "found" << endl;
        } else {
            cout << "not found" << endl;
        }
    }

    return 0;
}

Mohammed Muzahidul Islam - Medium

Thank you for your time. Do Follow and Share.