This documentation is automatically generated by competitive-verifier/competitive-verifier
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/point_add_range_sum
#include "../Segtree.cpp"
long long op(long long a, long long b) { return a + b; }
long long e() { return 0; }
int main() {
int n, q;
cin >> n >> q;
vector<long long> a(n);
for (long long &x : a) cin >> x;
segtree<long long, op, e> seg(a);
while (q--) {
int t, x, y;
cin >> t >> x >> y;
if (t == 0)
seg.add(x, y);
else
cout << seg.prod(x, y) << endl;
}
}
#line 1 "test/Segtree.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/point_add_range_sum
#line 1 "Segtree.cpp"
#include <bits/stdc++.h>
using namespace std;
template <class S, S (*op)(S, S), S (*e)()>
struct segtree {
int siz = 1;
vector<S> dat;
segtree(int n) : segtree(vector<S>(n, e())) {}
segtree(const vector<S>& a) {
while (siz < a.size()) siz <<= 1;
dat = vector<S>(siz << 1, e());
for (int i = 0; i < a.size(); i++) dat[siz + i] = a[i];
for (int i = siz - 1; i >= 1; i--) dat[i] = op(dat[2 * i], dat[2 * i + 1]);
}
void set(int p, S x) {
p += siz;
dat[p] = x;
while (p > 0) {
p >>= 1;
dat[p] = op(dat[2 * p], dat[2 * p + 1]);
}
}
void add(int p, S x) { set(p, get(p) + x); }
S get(int p) { return dat[p + siz]; }
S prod(int l, int r) {
S vl = e(), vr = e();
l += siz, r += siz;
while (l < r) {
if (l & 1) vl = op(vl, dat[l++]);
if (r & 1) vr = op(dat[--r], vr);
l >>= 1, r >>= 1;
}
return op(vl, vr);
}
S all_prod() { return dat[1]; }
};
#line 3 "test/Segtree.test.cpp"
long long op(long long a, long long b) { return a + b; }
long long e() { return 0; }
int main() {
int n, q;
cin >> n >> q;
vector<long long> a(n);
for (long long &x : a) cin >> x;
segtree<long long, op, e> seg(a);
while (q--) {
int t, x, y;
cin >> t >> x >> y;
if (t == 0)
seg.add(x, y);
else
cout << seg.prod(x, y) << endl;
}
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | example_00 |
![]() |
5 ms | 4 MB |
g++ | max_random_00 |
![]() |
721 ms | 15 MB |
g++ | max_random_01 |
![]() |
786 ms | 15 MB |
g++ | max_random_02 |
![]() |
781 ms | 15 MB |
g++ | max_random_03 |
![]() |
790 ms | 15 MB |
g++ | max_random_04 |
![]() |
730 ms | 15 MB |
g++ | random_00 |
![]() |
701 ms | 15 MB |
g++ | random_01 |
![]() |
683 ms | 15 MB |
g++ | random_02 |
![]() |
958 ms | 5 MB |
g++ | random_03 |
![]() |
177 ms | 15 MB |
g++ | random_04 |
![]() |
241 ms | 14 MB |
g++ | small_00 |
![]() |
6 ms | 4 MB |
g++ | small_01 |
![]() |
6 ms | 4 MB |
g++ | small_02 |
![]() |
6 ms | 4 MB |
g++ | small_03 |
![]() |
6 ms | 3 MB |
g++ | small_04 |
![]() |
6 ms | 4 MB |
g++ | small_05 |
![]() |
5 ms | 3 MB |
g++ | small_06 |
![]() |
6 ms | 4 MB |
g++ | small_07 |
![]() |
6 ms | 4 MB |
g++ | small_08 |
![]() |
5 ms | 3 MB |
g++ | small_09 |
![]() |
5 ms | 4 MB |
clang++ | example_00 |
![]() |
5 ms | 4 MB |
clang++ | max_random_00 |
![]() |
756 ms | 15 MB |
clang++ | max_random_01 |
![]() |
807 ms | 15 MB |
clang++ | max_random_02 |
![]() |
763 ms | 15 MB |
clang++ | max_random_03 |
![]() |
726 ms | 15 MB |
clang++ | max_random_04 |
![]() |
806 ms | 15 MB |
clang++ | random_00 |
![]() |
659 ms | 14 MB |
clang++ | random_01 |
![]() |
666 ms | 15 MB |
clang++ | random_02 |
![]() |
567 ms | 5 MB |
clang++ | random_03 |
![]() |
170 ms | 15 MB |
clang++ | random_04 |
![]() |
205 ms | 14 MB |
clang++ | small_00 |
![]() |
6 ms | 4 MB |
clang++ | small_01 |
![]() |
6 ms | 4 MB |
clang++ | small_02 |
![]() |
6 ms | 3 MB |
clang++ | small_03 |
![]() |
6 ms | 3 MB |
clang++ | small_04 |
![]() |
6 ms | 4 MB |
clang++ | small_05 |
![]() |
5 ms | 4 MB |
clang++ | small_06 |
![]() |
5 ms | 4 MB |
clang++ | small_07 |
![]() |
6 ms | 3 MB |
clang++ | small_08 |
![]() |
6 ms | 3 MB |
clang++ | small_09 |
![]() |
5 ms | 3 MB |