library/test/aoj/DSL_2_B-RSQ.fenwick.test.cpp

• View this file on GitHub
• Last update: 2024-03-25 12:22:53+06:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_B

Depends on

• Fenwick Tree (library/ds/fenwickTree.hpp)

Code

#include <bits/stdc++.h>
using namespace std;
#include "../../ds/fenwickTree.hpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_B"

int main() {
    ios_base::sync_with_stdio(0);
    int n, q;
    cin>>n>>q;
    FenwickTree<long long> ft(n);

    while(q--) {
        int typ;
        cin>>typ;
        if(typ==0) {
            int id, x;
            cin>>id>>x;
            ft.add(id, x);
        } else {
            int a, b;
            cin>>a>>b;
            cout<<ft.sum(a, b)<<'\n';
        }
    }
    return 0;
}

#line 1 "library/test/aoj/DSL_2_B-RSQ.fenwick.test.cpp"
#include <bits/stdc++.h>
using namespace std;
#line 2 "library/ds/fenwickTree.hpp"

template <class T> struct FenwickTree { // 1 indexed
    int n;
    vector<T> data;
    FenwickTree() : n(0) {}
    FenwickTree(int n) : n(n), data(n + 1, 0) {}

    // a[id] += x and all the ranges responsible for 'id', O(log(n))
    // x = i&-i => lsb(x); lsb(0b1101000) = 0b1000 = 8
    void add(int id, T x) {
        for (int i = id; i <= n; i += i & -i) {
            data[i] += x;
        }
    }
    void range_add(int l, int r, T val) {
        add(l, val);
        add(r + 1, -val);
    }

    // prefix sum from [1, r], O(log(n))
    T sum(int r) {
        T s(0);
        for (int i = r; i > 0; i -= i & -i) {
            s += data[i];
        }
        return s;
    }
    // [l, r]
    T sum(int l, int r) { return sum(r) - sum(l - 1); }
};
#line 4 "library/test/aoj/DSL_2_B-RSQ.fenwick.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_B"

int main() {
    ios_base::sync_with_stdio(0);
    int n, q;
    cin>>n>>q;
    FenwickTree<long long> ft(n);

    while(q--) {
        int typ;
        cin>>typ;
        if(typ==0) {
            int id, x;
            cin>>id>>x;
            ft.add(id, x);
        } else {
            int a, b;
            cin>>a>>b;
            cout<<ft.sum(a, b)<<'\n';
        }
    }
    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_small_00.in	AC	6 ms	4 MB
g++	00_small_01.in	AC	6 ms	4 MB
g++	00_small_02.in	AC	5 ms	4 MB
g++	00_small_03.in	AC	6 ms	4 MB
g++	01_rand_00.in	AC	6 ms	4 MB
g++	01_rand_01.in	AC	6 ms	4 MB
g++	01_rand_02.in	AC	6 ms	4 MB
g++	01_rand_03.in	AC	6 ms	4 MB
g++	02_slight_00.in	AC	6 ms	4 MB
g++	02_slight_01.in	AC	6 ms	4 MB
g++	02_slight_02.in	AC	7 ms	4 MB
g++	02_slight_03.in	AC	20 ms	4 MB
g++	03_biased_00.in	AC	6 ms	4 MB
g++	03_biased_01.in	AC	57 ms	4 MB
g++	03_biased_02.in	AC	49 ms	4 MB
g++	03_biased_03.in	AC	70 ms	4 MB
g++	04_maximum_00.in	AC	96 ms	4 MB
g++	04_maximum_01.in	AC	117 ms	4 MB
g++	04_maximum_02.in	AC	75 ms	4 MB
g++	04_maximum_03.in	AC	94 ms	4 MB

Back to top page