This documentation is automatically generated by competitive-verifier/competitive-verifier
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/point_add_range_sum
#include "../BIT.cpp"
using ll = long long;
int main() {
int n, q;
cin >> n >> q;
BIT<ll> bit(n);
for (int i = 0; i < n; i++) {
int a;
cin >> a;
bit.add(i + 1, a);
}
while (q--) {
int t;
cin >> t;
if (t == 0) {
int p, x;
cin >> p >> x;
bit.add(p + 1, x);
} else {
int l, r;
cin >> l >> r;
cout << bit.sum(l + 1, r) << endl;
}
}
}
#line 1 "test/BIT.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/point_add_range_sum
#line 1 "BIT.cpp"
#include <bits/stdc++.h>
using namespace std;
template <class T>
struct BIT {
// 1-indexed
int n, beki = 1;
vector<T> bit;
BIT(int x) {
bit.resize(x + 1, 0);
n = x;
while (beki * 2 <= n) beki *= 2;
}
T sum(int i) {
T res = 0;
while (i > 0) {
res += bit[i];
i -= i & -i;
}
return res;
}
T sum(int l, int r) {
//[l,r]
return sum(r) - (l == 0 ? 0 : sum(l - 1));
}
void add(int i, T x) {
while (i <= n) {
bit[i] += x;
i += i & -i;
}
}
int lowerbound(T w) {
if (w <= 0) return 0;
int x = 0;
for (int k = beki; k > 0; k >>= 1) {
if (x + k <= n && bit[x + k] < w) {
w -= bit[x + k];
x += k;
}
}
return x + 1;
}
};
#line 3 "test/BIT.test.cpp"
using ll = long long;
int main() {
int n, q;
cin >> n >> q;
BIT<ll> bit(n);
for (int i = 0; i < n; i++) {
int a;
cin >> a;
bit.add(i + 1, a);
}
while (q--) {
int t;
cin >> t;
if (t == 0) {
int p, x;
cin >> p >> x;
bit.add(p + 1, x);
} else {
int l, r;
cin >> l >> r;
cout << bit.sum(l + 1, r) << endl;
}
}
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | example_00 |
![]() |
5 ms | 4 MB |
g++ | max_random_00 |
![]() |
756 ms | 7 MB |
g++ | max_random_01 |
![]() |
710 ms | 7 MB |
g++ | max_random_02 |
![]() |
722 ms | 7 MB |
g++ | max_random_03 |
![]() |
690 ms | 7 MB |
g++ | max_random_04 |
![]() |
686 ms | 7 MB |
g++ | random_00 |
![]() |
589 ms | 6 MB |
g++ | random_01 |
![]() |
638 ms | 7 MB |
g++ | random_02 |
![]() |
428 ms | 4 MB |
g++ | random_03 |
![]() |
157 ms | 7 MB |
g++ | random_04 |
![]() |
189 ms | 5 MB |
g++ | small_00 |
![]() |
5 ms | 4 MB |
g++ | small_01 |
![]() |
5 ms | 4 MB |
g++ | small_02 |
![]() |
5 ms | 3 MB |
g++ | small_03 |
![]() |
5 ms | 4 MB |
g++ | small_04 |
![]() |
5 ms | 4 MB |
g++ | small_05 |
![]() |
5 ms | 4 MB |
g++ | small_06 |
![]() |
5 ms | 4 MB |
g++ | small_07 |
![]() |
5 ms | 3 MB |
g++ | small_08 |
![]() |
6 ms | 3 MB |
g++ | small_09 |
![]() |
6 ms | 3 MB |
clang++ | example_00 |
![]() |
5 ms | 4 MB |
clang++ | max_random_00 |
![]() |
726 ms | 7 MB |
clang++ | max_random_01 |
![]() |
749 ms | 7 MB |
clang++ | max_random_02 |
![]() |
735 ms | 7 MB |
clang++ | max_random_03 |
![]() |
721 ms | 7 MB |
clang++ | max_random_04 |
![]() |
723 ms | 7 MB |
clang++ | random_00 |
![]() |
695 ms | 6 MB |
clang++ | random_01 |
![]() |
594 ms | 7 MB |
clang++ | random_02 |
![]() |
515 ms | 4 MB |
clang++ | random_03 |
![]() |
174 ms | 7 MB |
clang++ | random_04 |
![]() |
190 ms | 5 MB |
clang++ | small_00 |
![]() |
5 ms | 3 MB |
clang++ | small_01 |
![]() |
6 ms | 3 MB |
clang++ | small_02 |
![]() |
5 ms | 4 MB |
clang++ | small_03 |
![]() |
5 ms | 4 MB |
clang++ | small_04 |
![]() |
5 ms | 3 MB |
clang++ | small_05 |
![]() |
5 ms | 4 MB |
clang++ | small_06 |
![]() |
5 ms | 4 MB |
clang++ | small_07 |
![]() |
5 ms | 3 MB |
clang++ | small_08 |
![]() |
5 ms | 4 MB |
clang++ | small_09 |
![]() |
5 ms | 4 MB |