test/aoj/DSL_2_G.range_fenwick_tree.test.cpp

• View this file on GitHub
• Last update: 2024-01-08 02:22:28+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G

Depends on

• Fenwick Tree with Range Update (data-structure/range_fenwick_tree.hpp)

Code

#define PROBLEM \
    "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G"

#include <bits/stdc++.h>

#include "../../data-structure/range_fenwick_tree.hpp"
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    RangeFenwickTree<long long> ft(n + 1);
    for (int i = 0; i < q; i++) {
        int type, s, t;
        cin >> type >> s >> t;
        --s;
        --t;
        if (type == 0) {
            int x;
            cin >> x;
            ft.add(s, t + 1, x);
        } else {
            cout << ft.prefix_sum(t + 1) - ft.prefix_sum(s) << "\n";
        }
    }
}

#line 1 "test/aoj/DSL_2_G.range_fenwick_tree.test.cpp"
#define PROBLEM \
    "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G"

#include <bits/stdc++.h>

#line 3 "data-structure/range_fenwick_tree.hpp"

template <typename T>
class RangeFenwickTree {
   public:
    RangeFenwickTree() = default;
    explicit RangeFenwickTree(int n) : n(n), data0(n + 1), data1(n + 1) {}

    T prefix_sum(int i) const {
        return prefix_sum(data0, i) * (i - 1) + prefix_sum(data1, i);
    }

    void add(int l, int r, T x) {
        add(data0, l, x);
        add(data0, r, -x);
        add(data1, l, -x * (l - 1));
        add(data1, r, x * (r - 1));
    }

   private:
    int n;
    std::vector<T> data0, data1;

    T prefix_sum(const std::vector<T>& data, int i) const {
        T ret = 0;
        for (; i > 0; i -= i & -i) ret += data[i];
        return ret;
    }

    void add(std::vector<T>& data, int i, T x) {
        for (++i; i <= n; i += i & -i) data[i] += x;
    }
};
#line 7 "test/aoj/DSL_2_G.range_fenwick_tree.test.cpp"
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    RangeFenwickTree<long long> ft(n + 1);
    for (int i = 0; i < q; i++) {
        int type, s, t;
        cin >> type >> s >> t;
        --s;
        --t;
        if (type == 0) {
            int x;
            cin >> x;
            ft.add(s, t + 1, x);
        } else {
            cout << ft.prefix_sum(t + 1) - ft.prefix_sum(s) << "\n";
        }
    }
}

Back to top page