datastructure/CumulativeSum.hpp

• View this file on GitHub
• Last update: 2021-05-27 02:04:57+09:00
• Include: #include "datastructure/CumulativeSum.hpp"

Verified with

• test/static-range-sum.test.cpp

Code

#include <vector>
#include <cassert>
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 1 "datastructure/CumulativeSum.hpp"
#include <vector>
#include <cassert>
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]; 
  }
};

Back to top page