test/fwtree2.test.cpp

• View this file on GitHub
• Last update: 2024-03-03 06:51:22+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_E

Depends on

• Binary Indexed Tree (C++/ds/fwtree/FenwickTree.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_E"
#include <iostream>
#include "C++/ds/fwtree/FenwickTree.hpp"
int main() {
    std::cin.tie(nullptr) -> sync_with_stdio(false);
    int n, q;
    std::cin >> n >> q;
    FenwickTree<int64_t> bit(n);
    while(q--) {
        int h;
        std::cin >> h;
        if(h == 0) {
            int s, t, x;
            std::cin >> s >> t >> x;
            bit.add(--s, --t, x);
        } else {
            int i;
            std::cin >> i;
            std::cout << bit.sum(--i) << '\n';
        }
    }
}

#line 1 "test/fwtree2.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_E"
#include <iostream>
#line 2 "C++/ds/fwtree/FenwickTree.hpp"

#include <vector>

template <class T> struct FenwickTree {
private:
    int n;
    std::vector<T> data;
    void init(const size_t size) {
        n = size + 2;
        data.resize(n + 1);
    }
public:
    FenwickTree(){}
    FenwickTree(const size_t size){ init(size); }
    FenwickTree(const std::vector<T> &a) {
        init(a.size());
        for(size_t i = 0; i < a.size(); ++i) {
            add(i, a[i]);
        }
    }
    T sum(int k) const {
        if(k < 0) {
            return 0;
        }
        T ret = 0;
        for(++k; k > 0; k -= k & -k) {
            ret += data[k];
        }
        return ret;
    }
    inline T sum(int l, int r) const { return sum(r) - sum(l - 1); }
    inline T operator[](int k) const { return sum(k) - sum(k - 1); }
    void add(int k, const T &x) {
        for(++k; k < n; k += k & -k) {
            data[k] += x;
        }
    }
    void add(const int l, const int r, const T& x) {
        add(l, x);
        add(r + 1, -x);
    }
    int lower_bound(T w) {
        if(w <= 0) {
            return 0;
        }
        int x = 0;
        for(int k = 1 << std::__lg(n); k; k >>= 1) {
            if(x + k <= n - 1 && data[x + k] < w) {
                w -= data[x + k];
                x += k;
            }
        }
        return x;
    }
    int upper_bound(T w) {
        if(w < 0) {
            return 0;
        }
        int x = 0;
        for(int k = 1 << std::__lg(n); k; k >>= 1) {
            if(x + k <= n - 1 && data[x + k] <= w) {
                w -= data[x + k];
                x += k;
            }
        }
        return x;
    }
};

/**
 * @brief Binary Indexed Tree
 * @see https://nyaannyaan.github.io/library/data-structure/binary-indexed-tree.hpp
 */
#line 4 "test/fwtree2.test.cpp"
int main() {
    std::cin.tie(nullptr) -> sync_with_stdio(false);
    int n, q;
    std::cin >> n >> q;
    FenwickTree<int64_t> bit(n);
    while(q--) {
        int h;
        std::cin >> h;
        if(h == 0) {
            int s, t, x;
            std::cin >> s >> t >> x;
            bit.add(--s, --t, x);
        } else {
            int i;
            std::cin >> i;
            std::cout << bit.sum(--i) << '\n';
        }
    }
}

Back to top page