Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub anmichi/Library

:heavy_check_mark: test/BIT.test.cpp

Depends on

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 :heavy_check_mark: AC 5 ms 4 MB
g++ max_random_00 :heavy_check_mark: AC 756 ms 7 MB
g++ max_random_01 :heavy_check_mark: AC 710 ms 7 MB
g++ max_random_02 :heavy_check_mark: AC 722 ms 7 MB
g++ max_random_03 :heavy_check_mark: AC 690 ms 7 MB
g++ max_random_04 :heavy_check_mark: AC 686 ms 7 MB
g++ random_00 :heavy_check_mark: AC 589 ms 6 MB
g++ random_01 :heavy_check_mark: AC 638 ms 7 MB
g++ random_02 :heavy_check_mark: AC 428 ms 4 MB
g++ random_03 :heavy_check_mark: AC 157 ms 7 MB
g++ random_04 :heavy_check_mark: AC 189 ms 5 MB
g++ small_00 :heavy_check_mark: AC 5 ms 4 MB
g++ small_01 :heavy_check_mark: AC 5 ms 4 MB
g++ small_02 :heavy_check_mark: AC 5 ms 3 MB
g++ small_03 :heavy_check_mark: AC 5 ms 4 MB
g++ small_04 :heavy_check_mark: AC 5 ms 4 MB
g++ small_05 :heavy_check_mark: AC 5 ms 4 MB
g++ small_06 :heavy_check_mark: AC 5 ms 4 MB
g++ small_07 :heavy_check_mark: AC 5 ms 3 MB
g++ small_08 :heavy_check_mark: AC 6 ms 3 MB
g++ small_09 :heavy_check_mark: AC 6 ms 3 MB
clang++ example_00 :heavy_check_mark: AC 5 ms 4 MB
clang++ max_random_00 :heavy_check_mark: AC 726 ms 7 MB
clang++ max_random_01 :heavy_check_mark: AC 749 ms 7 MB
clang++ max_random_02 :heavy_check_mark: AC 735 ms 7 MB
clang++ max_random_03 :heavy_check_mark: AC 721 ms 7 MB
clang++ max_random_04 :heavy_check_mark: AC 723 ms 7 MB
clang++ random_00 :heavy_check_mark: AC 695 ms 6 MB
clang++ random_01 :heavy_check_mark: AC 594 ms 7 MB
clang++ random_02 :heavy_check_mark: AC 515 ms 4 MB
clang++ random_03 :heavy_check_mark: AC 174 ms 7 MB
clang++ random_04 :heavy_check_mark: AC 190 ms 5 MB
clang++ small_00 :heavy_check_mark: AC 5 ms 3 MB
clang++ small_01 :heavy_check_mark: AC 6 ms 3 MB
clang++ small_02 :heavy_check_mark: AC 5 ms 4 MB
clang++ small_03 :heavy_check_mark: AC 5 ms 4 MB
clang++ small_04 :heavy_check_mark: AC 5 ms 3 MB
clang++ small_05 :heavy_check_mark: AC 5 ms 4 MB
clang++ small_06 :heavy_check_mark: AC 5 ms 4 MB
clang++ small_07 :heavy_check_mark: AC 5 ms 3 MB
clang++ small_08 :heavy_check_mark: AC 5 ms 4 MB
clang++ small_09 :heavy_check_mark: AC 5 ms 4 MB
Back to top page