data_structure/binary_indexed_tree.test.cpp

View this file on GitHub
Last update: 2021-08-30 04:35:37+09:00
Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#include <cstdio>
#include <tuple>
#include <vector>
#include "../data_structure/binary_indexed_tree.hpp"
#include "../monoids/plus.hpp"
#include "../utils/macros.hpp"
using namespace std;

int main() {
    int n, q; scanf("%d%d", &n, &q);
    vector<long long> a(n);
    REP (i, n) {
        scanf("%lld", &a[i]);
    }
    binary_indexed_tree<plus_monoid<long long> > bit(ALL(a));
    while (q --) {
        int t, x, y; scanf("%d%d%d", &t, &x, &y);
        if (t == 0) {
            bit.point_mult(x, y);
        } else if (t == 1) {
            long long answer = bit.initial_range_get(y) - bit.initial_range_get(x);
            printf("%lld\n", answer);
        }
    }
    return 0;
}

#line 1 "data_structure/binary_indexed_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#include <cstdio>
#include <tuple>
#include <vector>
#line 2 "data_structure/binary_indexed_tree.hpp"
#include <cassert>
#line 2 "utils/macros.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
#line 5 "data_structure/binary_indexed_tree.hpp"

/**
 * @brief Binary Indexed Tree
 */
template <typename CommutativeMonoid>
struct binary_indexed_tree {
    typedef typename CommutativeMonoid::value_type value_type;
    CommutativeMonoid mon;
    std::vector<value_type> data;
    binary_indexed_tree(int n, CommutativeMonoid const & mon_ = CommutativeMonoid())
            : mon(mon_),
              data(n, mon.unit()) {
    }
    template <class InputIterator>
    binary_indexed_tree(InputIterator first, InputIterator last, CommutativeMonoid const & mon_ = CommutativeMonoid())
            : mon(mon_),
              data(first, last) {
        REP3 (j, 1, data.size() + 1) {
            int k = j + (j & -j);
            if (k - 1 < static_cast<int>(data.size())) {
                data[k - 1] = mon.mult(data[k - 1], data[j - 1]);
            }
        }
    }
    /**
     * @note $a_i \gets a_i + z$
     * @note $O(\log N)$
     */
    void point_mult(int i, value_type z) {
        assert (0 <= i and i < static_cast<int>(data.size()));
        for (int j = i + 1; j <= static_cast<int>(data.size()); j += j & -j) {
            data[j - 1] = mon.mult(data[j - 1], z);
        }
    }
    /**
     * @note $\sum _ {i \lt r} a_i$
     * @note $O(\log N)$
     */
    value_type initial_range_get(int r) {
        assert (0 <= r and r <= static_cast<int>(data.size()));
        value_type acc = mon.unit();
        for (int i = r; 0 < i; i -= i & -i) {
            acc = mon.mult(data[i - 1], acc);
        }
        return acc;
    }
};
#line 2 "monoids/plus.hpp"

template <class T>
struct plus_monoid {
    typedef T value_type;
    value_type unit() const { return value_type(); }
    value_type mult(value_type a, value_type b) const { return a + b; }
};
#line 8 "data_structure/binary_indexed_tree.test.cpp"
using namespace std;

int main() {
    int n, q; scanf("%d%d", &n, &q);
    vector<long long> a(n);
    REP (i, n) {
        scanf("%lld", &a[i]);
    }
    binary_indexed_tree<plus_monoid<long long> > bit(ALL(a));
    while (q --) {
        int t, x, y; scanf("%d%d%d", &t, &x, &y);
        if (t == 0) {
            bit.point_mult(x, y);
        } else if (t == 1) {
            long long answer = bit.initial_range_get(y) - bit.initial_range_get(x);
            printf("%lld\n", answer);
        }
    }
    return 0;
}