test/binary_search.test.cpp

• View this file on GitHub
• Last update: 2025-08-05 17:07:01+09:00
• Problem: https://judge.yosupo.jp/problem/static_range_sum

Depends on

• Binary Search implementation (data_structure/binary_search.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"

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

#include "../data_structure/binary_search.hpp"

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N, Q;
    cin >> N >> Q;
    
    vector<ll> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    
    // Create prefix sum array
    vector<ll> prefix(N + 1, 0);
    for (int i = 0; i < N; i++) {
        prefix[i + 1] = prefix[i] + A[i];
    }
    
    // Use binary search to find the answer (just for testing)
    BinarySearch<ll> bs(prefix);
    
    for (int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
        
        // Calculate sum using prefix sum
        ll sum = prefix[r] - prefix[l];
        cout << sum << "\n";
    }
    
    return 0;
} 

#line 1 "test/binary_search.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"

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

#line 3 "data_structure/binary_search.hpp"
using namespace std;

/**
 * @brief Binary Search implementation
 * @tparam T Type of elements
 */
template<typename T>
class BinarySearch {
private:
    vector<T> data;

public:
    /**
     * @brief Constructor
     * @param vec Input vector (must be sorted)
     */
    BinarySearch(const vector<T>& vec) : data(vec) {}

    /**
     * @brief Find the first element >= target
     * @param target Target value
     * @return Index of first element >= target, or data.size() if not found
     */
    int lower_bound(T target) const {
        int left = 0, right = data.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (data[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    /**
     * @brief Find the first element > target
     * @param target Target value
     * @return Index of first element > target, or data.size() if not found
     */
    int upper_bound(T target) const {
        int left = 0, right = data.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (data[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    /**
     * @brief Check if target exists in the array
     * @param target Target value
     * @return true if found, false otherwise
     */
    bool contains(T target) const {
        int idx = lower_bound(target);
        return idx < data.size() && data[idx] == target;
    }
}; 
#line 8 "test/binary_search.test.cpp"

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N, Q;
    cin >> N >> Q;
    
    vector<ll> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    
    // Create prefix sum array
    vector<ll> prefix(N + 1, 0);
    for (int i = 0; i < N; i++) {
        prefix[i + 1] = prefix[i] + A[i];
    }
    
    // Use binary search to find the answer (just for testing)
    BinarySearch<ll> bs(prefix);
    
    for (int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
        
        // Calculate sum using prefix sum
        ll sum = prefix[r] - prefix[l];
        cout << sum << "\n";
    }
    
    return 0;
} 

Back to top page