test/Segtree.test.cpp

• View this file on GitHub
• Last update: 2025-07-04 15:57:54+09:00
• Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

• Segtree.cpp

Code

// 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;
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	max_random_00	AC	721 ms	15 MB
g++	max_random_01	AC	786 ms	15 MB
g++	max_random_02	AC	781 ms	15 MB
g++	max_random_03	AC	790 ms	15 MB
g++	max_random_04	AC	730 ms	15 MB
g++	random_00	AC	701 ms	15 MB
g++	random_01	AC	683 ms	15 MB
g++	random_02	AC	958 ms	5 MB
g++	random_03	AC	177 ms	15 MB
g++	random_04	AC	241 ms	14 MB
g++	small_00	AC	6 ms	4 MB
g++	small_01	AC	6 ms	4 MB
g++	small_02	AC	6 ms	4 MB
g++	small_03	AC	6 ms	3 MB
g++	small_04	AC	6 ms	4 MB
g++	small_05	AC	5 ms	3 MB
g++	small_06	AC	6 ms	4 MB
g++	small_07	AC	6 ms	4 MB
g++	small_08	AC	5 ms	3 MB
g++	small_09	AC	5 ms	4 MB
clang++	example_00	AC	5 ms	4 MB
clang++	max_random_00	AC	756 ms	15 MB
clang++	max_random_01	AC	807 ms	15 MB
clang++	max_random_02	AC	763 ms	15 MB
clang++	max_random_03	AC	726 ms	15 MB
clang++	max_random_04	AC	806 ms	15 MB
clang++	random_00	AC	659 ms	14 MB
clang++	random_01	AC	666 ms	15 MB
clang++	random_02	AC	567 ms	5 MB
clang++	random_03	AC	170 ms	15 MB
clang++	random_04	AC	205 ms	14 MB
clang++	small_00	AC	6 ms	4 MB
clang++	small_01	AC	6 ms	4 MB
clang++	small_02	AC	6 ms	3 MB
clang++	small_03	AC	6 ms	3 MB
clang++	small_04	AC	6 ms	4 MB
clang++	small_05	AC	5 ms	4 MB
clang++	small_06	AC	5 ms	4 MB
clang++	small_07	AC	6 ms	3 MB
clang++	small_08	AC	6 ms	3 MB
clang++	small_09	AC	5 ms	3 MB

Back to top page