segmenttree/test/point-add-range-sum.test.cpp

• View this file on GitHub
• Last update: 2021-11-06 11:36:55+09:00
• Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

• Binary indexed tree / Fenwick tree （BIT・フェニック木） (segmenttree/binary_indexed_tree.hpp)

Code

#include "../binary_indexed_tree.hpp"
#include <iostream>
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"

// PointAddRangeSum (BIT based) 0-indexed
// Complexity: O(lg N) for each query
template <typename T> struct PointAddRangeSum {
    BIT<T> bit;
    PointAddRangeSum(const std::vector<T> &A) : bit(A.size()) {
        for (unsigned i = 0; i < A.size(); i++) bit.add(i, A[i]);
    }
    void add(int i, T val) { bit.add(i, val); }
    // sum [l, r)
    T get(int l, int r) const { return bit.sum(l, r); }
};

int main() {
    std::cin.tie(nullptr), std::ios::sync_with_stdio(false);

    int N, Q;
    std::cin >> N >> Q;
    std::vector<long long> A(N);
    for (auto &a : A) std::cin >> a;
    PointAddRangeSum<long long> s(A);
    while (Q--) {
        int q, l, r;
        std::cin >> q >> l >> r;
        if (q) {
            std::cout << s.get(l, r) << '\n';
        } else {
            s.add(l, r);
        }
    }
}

#line 2 "segmenttree/binary_indexed_tree.hpp"
#include <algorithm>
#include <vector>

// CUT begin
// 0-indexed BIT (binary indexed tree / Fenwick tree) (i : [0, len))
template <class T> struct BIT {
    int n;
    std::vector<T> data;
    BIT(int len = 0) : n(len), data(len) {}
    void reset() { std::fill(data.begin(), data.end(), T(0)); }
    void add(int pos, T v) { // a[pos] += v
        pos++;
        while (pos > 0 and pos <= n) data[pos - 1] += v, pos += pos & -pos;
    }
    T sum(int k) const { // a[0] + ... + a[k - 1]
        T res = 0;
        while (k > 0) res += data[k - 1], k -= k & -k;
        return res;
    }

    T sum(int l, int r) const { return sum(r) - sum(l); } // a[l] + ... + a[r - 1]

    template <class OStream> friend OStream &operator<<(OStream &os, const BIT &bit) {
        T prv = 0;
        os << '[';
        for (int i = 1; i <= bit.n; i++) {
            T now = bit.sum(i);
            os << now - prv << ',', prv = now;
        }
        return os << ']';
    }
};
#line 2 "segmenttree/test/point-add-range-sum.test.cpp"
#include <iostream>
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"

// PointAddRangeSum (BIT based) 0-indexed
// Complexity: O(lg N) for each query
template <typename T> struct PointAddRangeSum {
    BIT<T> bit;
    PointAddRangeSum(const std::vector<T> &A) : bit(A.size()) {
        for (unsigned i = 0; i < A.size(); i++) bit.add(i, A[i]);
    }
    void add(int i, T val) { bit.add(i, val); }
    // sum [l, r)
    T get(int l, int r) const { return bit.sum(l, r); }
};

int main() {
    std::cin.tie(nullptr), std::ios::sync_with_stdio(false);

    int N, Q;
    std::cin >> N >> Q;
    std::vector<long long> A(N);
    for (auto &a : A) std::cin >> a;
    PointAddRangeSum<long long> s(A);
    while (Q--) {
        int q, l, r;
        std::cin >> q >> l >> r;
        if (q) {
            std::cout << s.get(l, r) << '\n';
        } else {
            s.add(l, r);
        }
    }
}

Back to top page