test/yosupo/point_add_range_sum.BIT.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 12:11:12+09:00
• Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

• Binary Indexed Tree (src/DataStructure/BinaryIndexedTree.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/point_add_range_sum
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include "src/DataStructure/BinaryIndexedTree.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 BinaryIndexedTree<long long> bit(N);
 for (int i= 0; i < N; i++) {
  long long a;
  cin >> a;
  bit.add(i, a);
 }
 while (Q--) {
  int t, a, b;
  cin >> t >> a >> b;
  if (t) cout << bit.sum(a, b) << '\n';
  else bit.add(a, b);
 }
}

#line 1 "test/yosupo/point_add_range_sum.BIT.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/point_add_range_sum
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#line 2 "src/DataStructure/BinaryIndexedTree.hpp"
#include <algorithm>
#include <vector>
template <typename T> class BinaryIndexedTree {
 std::vector<T> dat;
public:
 BinaryIndexedTree(int n): dat(n + 1, T()) {}
 BinaryIndexedTree(int n, T a): BinaryIndexedTree(std::vector<T>(n, a)) {}
 BinaryIndexedTree(const std::vector<T>& y): dat(y.size() + 1, 0) {
  for (int i= y.size(); i--;) dat[i + 1]= y[i];
  for (int i= 1, e= dat.size(), j; i < e; ++i)
   if ((j= i + (i & -i)) < e) dat[j]+= dat[i];
 }
 void add(int i, T a= 1) {
  for (++i; i < (int)dat.size(); i+= i & -i) dat[i]+= a;
 }
 T sum(int i) const {  // sum [0,i)
  T s= 0;
  for (; i; i&= i - 1) s+= dat[i];
  return s;
 }
 T sum(int l, int r) const { return sum(r) - sum(l); }  // sum [l,r)
 T operator[](int k) const { return sum(k + 1) - sum(k); }
 int find(T k) const {  // min { i : sum(i+1) > k } -> kth element(0-indexed)
  int i= 0;
  for (int p= 1 << (std::__lg(dat.size() - 1) + 1), e= dat.size(); p; p>>= 1)
   if (i + p < e && dat[i + p] <= k) k-= dat[i+= p];
  return i + 1 == (int)dat.size() ? -1 : i;  // -1 -> no solutions
 }
};
#line 6 "test/yosupo/point_add_range_sum.BIT.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 BinaryIndexedTree<long long> bit(N);
 for (int i= 0; i < N; i++) {
  long long a;
  cin >> a;
  bit.add(i, a);
 }
 while (Q--) {
  int t, a, b;
  cin >> t >> a >> b;
  if (t) cout << bit.sum(a, b) << '\n';
  else bit.add(a, b);
 }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	example_00	AC	5 ms	4 MB
g++-13	max_random_00	AC	149 ms	7 MB
g++-13	max_random_01	AC	155 ms	7 MB
g++-13	max_random_02	AC	149 ms	7 MB
g++-13	max_random_03	AC	154 ms	7 MB
g++-13	max_random_04	AC	155 ms	7 MB
g++-13	random_00	AC	127 ms	6 MB
g++-13	random_01	AC	127 ms	7 MB
g++-13	random_02	AC	90 ms	4 MB
g++-13	random_03	AC	42 ms	7 MB
g++-13	random_04	AC	47 ms	6 MB
g++-13	small_00	AC	6 ms	4 MB
g++-13	small_01	AC	5 ms	4 MB
g++-13	small_02	AC	5 ms	4 MB
g++-13	small_03	AC	5 ms	4 MB
g++-13	small_04	AC	5 ms	4 MB
g++-13	small_05	AC	4 ms	4 MB
g++-13	small_06	AC	5 ms	4 MB
g++-13	small_07	AC	5 ms	4 MB
g++-13	small_08	AC	5 ms	4 MB
g++-13	small_09	AC	5 ms	4 MB
clang++-18	example_00	AC	8 ms	4 MB
clang++-18	max_random_00	AC	161 ms	7 MB
clang++-18	max_random_01	AC	151 ms	7 MB
clang++-18	max_random_02	AC	155 ms	7 MB
clang++-18	max_random_03	AC	158 ms	7 MB
clang++-18	max_random_04	AC	158 ms	7 MB
clang++-18	random_00	AC	126 ms	6 MB
clang++-18	random_01	AC	128 ms	7 MB
clang++-18	random_02	AC	86 ms	4 MB
clang++-18	random_03	AC	41 ms	7 MB
clang++-18	random_04	AC	48 ms	6 MB
clang++-18	small_00	AC	6 ms	4 MB
clang++-18	small_01	AC	5 ms	4 MB
clang++-18	small_02	AC	5 ms	4 MB
clang++-18	small_03	AC	5 ms	4 MB
clang++-18	small_04	AC	5 ms	4 MB
clang++-18	small_05	AC	5 ms	4 MB
clang++-18	small_06	AC	5 ms	4 MB
clang++-18	small_07	AC	5 ms	4 MB
clang++-18	small_08	AC	5 ms	4 MB
clang++-18	small_09	AC	5 ms	4 MB

Back to top page