test/data_structure/Point_Add_Range_Sum_BIT.test.cpp

View this file on GitHub
Last update: 2023-12-28 15:52:36+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 <iostream>


#include "../../data_structure/fenwick_tree.hpp"

#include "../../template/int_alias.hpp"


using ebi::i64;

int main() {
    int n, q;
    std::cin >> n >> q;
    ebi::fenwick_tree<i64> fw(n);
    for (int i = 0; i < n; i++) {
        i64 a;
        std::cin >> a;
        fw.add(i, a);
    }
    for (int i = 0; i < q; i++) {
        int flag;
        std::cin >> flag;
        if (flag == 0) {
            int p;
            i64 x;
            std::cin >> p >> x;
            fw.add(p, x);
        } else {
            int l, r;
            std::cin >> l >> r;
            std::cout << fw.sum(l, r) << std::endl;
        }
    }
}

#line 1 "test/data_structure/Point_Add_Range_Sum_BIT.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"

#include <iostream>


#line 2 "data_structure/fenwick_tree.hpp"

#include <cassert>

#include <vector>


namespace ebi {

template <class T> struct fenwick_tree {
  private:
    int n;
    std::vector<T> data;

  public:
    fenwick_tree(int _n) : n(_n), data(std::vector<T>(_n + 1, T(0))) {}

    void add(int i, T val) {
        i++;
        for (int x = i; x <= n; x += x & -x) {
            data[x] += val;
        }
    }

    T prefix_sum(int i) const {
        assert(0 <= i && i <= n);
        T ret = 0;
        for (int x = i; x > 0; x -= x & -x) {
            ret += data[x];
        }
        return ret;
    }

    T sum(int l, int r) const {
        return prefix_sum(r) - prefix_sum(l);
    }

    T all_sum() const {
        return prefix_sum(n);
    }

    // prefix_sum(x) >= key となる最小のxを返す関数 O(log N)

    int lower_bound(T key) {
        if (key <= 0) return 0;
        int x = 0;
        int max = 1;
        while ((max << 1) <= n) max <<= 1;
        for (int k = max; k > 0; k >>= 1) {
            if (x + k <= n && data[x + k] < key) {
                x += k;
                key -= data[x];
            }
        }
        return x + 1;
    }
};

}  // namespace ebi
#line 2 "template/int_alias.hpp"

#include <cstdint>

namespace ebi {

using ld = long double;
using std::size_t;
using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using u16 = std::uint16_t;
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;

}  // namespace ebi
#line 7 "test/data_structure/Point_Add_Range_Sum_BIT.test.cpp"

using ebi::i64;

int main() {
    int n, q;
    std::cin >> n >> q;
    ebi::fenwick_tree<i64> fw(n);
    for (int i = 0; i < n; i++) {
        i64 a;
        std::cin >> a;
        fw.add(i, a);
    }
    for (int i = 0; i < q; i++) {
        int flag;
        std::cin >> flag;
        if (flag == 0) {
            int p;
            i64 x;
            std::cin >> p >> x;
            fw.add(p, x);
        } else {
            int l, r;
            std::cin >> l >> r;
            std::cout << fw.sum(l, r) << std::endl;
        }
    }
}