test/point-add-range-sum.test.cpp

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

Depends on

• datastructure/BIT.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#include <vector>
#include <cassert>
#include <iostream>
#include "../datastructure/BIT.hpp"
int main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int N, Q; std::cin >> N >> Q;
  BIT<long long> bit(N+1);
  for(int i=0; i<N; i++) {
    long long a; std::cin >> a;
    bit.add(i+1, a);
  }
  while(Q--) {
    int t; std::cin >> t;
    if(t == 0) {
      long long p, x; std::cin >> p >> x;
      bit.add(p+1, x);
    }else{
      int l, r; std::cin >> l >> r;
      std::cout << bit.rangesum(l+1, r) << '\n';
    }
  }
  return 0;
}

#line 1 "test/point-add-range-sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#include <vector>
#include <cassert>
#include <iostream>
#line 4 "datastructure/BIT.hpp"
template<typename T> 
struct BIT{
  int N;
  std::vector<T> node;

  BIT(int n){
    N = n;
    node.resize(N+10);
  }

  /* a: 1-indexed */
  void add(int a, T x){
    for(int i=a; i<(int)node.size(); i += i & -i) node[i] += x;
  }

  /* [1, a] */
  T sum(int a){
    T res = 0;
    for(int x=a; x>0; x -= x & -x) res += node[x];
    return res;
  }

  /* [l, r] */
  T rangesum(int l, int r){
    return sum(r) - sum(l-1);
  }

  /* 
    a1+a2+...+aw >= valとなるような最小のwを返す
    @verify https://codeforces.com/contest/992/problem/E
  */
  int lower_bound(T val) {
    if(val < 0) return 0;

    int res = 0;
    int n = 1; 
    while (n < N) n *= 2;

    T tv=0;
    for (int k = n; k > 0; k /= 2) {
      if(res + k < N && node[res + k] < val){
        val -= node[res+k];
        res += k;
      }
    }
    return res+1; 
  }
};
#line 6 "test/point-add-range-sum.test.cpp"
int main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int N, Q; std::cin >> N >> Q;
  BIT<long long> bit(N+1);
  for(int i=0; i<N; i++) {
    long long a; std::cin >> a;
    bit.add(i+1, a);
  }
  while(Q--) {
    int t; std::cin >> t;
    if(t == 0) {
      long long p, x; std::cin >> p >> x;
      bit.add(p+1, x);
    }else{
      int l, r; std::cin >> l >> r;
      std::cout << bit.rangesum(l+1, r) << '\n';
    }
  }
  return 0;
}

Back to top page