test/BIT.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

• BIT.cpp

Code

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

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	max_random_00	AC	756 ms	7 MB
g++	max_random_01	AC	710 ms	7 MB
g++	max_random_02	AC	722 ms	7 MB
g++	max_random_03	AC	690 ms	7 MB
g++	max_random_04	AC	686 ms	7 MB
g++	random_00	AC	589 ms	6 MB
g++	random_01	AC	638 ms	7 MB
g++	random_02	AC	428 ms	4 MB
g++	random_03	AC	157 ms	7 MB
g++	random_04	AC	189 ms	5 MB
g++	small_00	AC	5 ms	4 MB
g++	small_01	AC	5 ms	4 MB
g++	small_02	AC	5 ms	3 MB
g++	small_03	AC	5 ms	4 MB
g++	small_04	AC	5 ms	4 MB
g++	small_05	AC	5 ms	4 MB
g++	small_06	AC	5 ms	4 MB
g++	small_07	AC	5 ms	3 MB
g++	small_08	AC	6 ms	3 MB
g++	small_09	AC	6 ms	3 MB
clang++	example_00	AC	5 ms	4 MB
clang++	max_random_00	AC	726 ms	7 MB
clang++	max_random_01	AC	749 ms	7 MB
clang++	max_random_02	AC	735 ms	7 MB
clang++	max_random_03	AC	721 ms	7 MB
clang++	max_random_04	AC	723 ms	7 MB
clang++	random_00	AC	695 ms	6 MB
clang++	random_01	AC	594 ms	7 MB
clang++	random_02	AC	515 ms	4 MB
clang++	random_03	AC	174 ms	7 MB
clang++	random_04	AC	190 ms	5 MB
clang++	small_00	AC	5 ms	3 MB
clang++	small_01	AC	6 ms	3 MB
clang++	small_02	AC	5 ms	4 MB
clang++	small_03	AC	5 ms	4 MB
clang++	small_04	AC	5 ms	3 MB
clang++	small_05	AC	5 ms	4 MB
clang++	small_06	AC	5 ms	4 MB
clang++	small_07	AC	5 ms	3 MB
clang++	small_08	AC	5 ms	4 MB
clang++	small_09	AC	5 ms	4 MB

Back to top page