test/static-range-sum.test.cpp

• View this file on GitHub
• Last update: 2021-05-27 02:04:57+09:00
• Problem: https://judge.yosupo.jp/problem/static_range_sum

Depends on

• datastructure/CumulativeSum.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"
#include <iostream>
#include <cassert>
#include <vector>
#include "../datastructure/CumulativeSum.hpp"

int main(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int N, Q; 
  std::cin >> N >> Q;
  std::vector<long long> v(N);
  for(int i=0; i<N; i++) std::cin >> v[i];
  CumulativeSum<long long> a(v);
  while(Q--){
    int l, r;
    std::cin >> l >> r;
    std::cout << a[r]-a[l] << '\n';
  }
  return 0;
}

#line 1 "test/static-range-sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"
#include <iostream>
#include <cassert>
#include <vector>
#line 3 "datastructure/CumulativeSum.hpp"
template<typename T>
struct CumulativeSum{
  int N;
  std::vector<T> data;

  CumulativeSum() = default;

  CumulativeSum(int n) : N(n) {
    data.assign(N+1, 0);
  }

  CumulativeSum(const std::vector<T> &v) : N(v.size()){
    data.assign(N+1, 0);
    for(int i=0; i<N; i++) {
      data[i+1] = data[i] + v[i];
    }
  }

  void build(const std::vector<T> &v){
    N = v.size();
    data.assign(N+1, 0);
    for(int i=0; i<N; i++) {
      data[i+1] = data[i] + v[i];
    }
  }
  
  // sum[0, i)
  inline T operator[](int i) { 
    assert(i <= N);
    return data[i]; 
  }
};
#line 6 "test/static-range-sum.test.cpp"

int main(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int N, Q; 
  std::cin >> N >> Q;
  std::vector<long long> v(N);
  for(int i=0; i<N; i++) std::cin >> v[i];
  CumulativeSum<long long> a(v);
  while(Q--){
    int l, r;
    std::cin >> l >> r;
    std::cout << a[r]-a[l] << '\n';
  }
  return 0;
}

Back to top page