test/DataStructure/BIT_Point_Add_Range_Sum.test.cpp

• View this file on GitHub
• Last update: 2023-11-12 21:52:10+09:00
• Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

• BIT (src/DataStructure/BIT.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"

#include <iostream>
#include <vector>

#include "../../src/DataStructure/BIT.hpp"

int main() {
    int N, Q;
    std::cin >> N >> Q;

    std::vector<long long> A(N);
    lib::BIT<long long> bit(N);
    for (int i = 0; i < N; i++) {
        std::cin >> A[i];
        bit.add(i, A[i]);
    }

    for (int i = 0; i < Q; i++) {
        long long t, l, r;
        std::cin >> t >> l >> r;
        if (t == 0) {
            bit.add(l, r);
        }
        if (t == 1) {
            std::cout << bit.sum(l, r) << '\n';
        }
    }
}

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

#include <iostream>
#include <vector>

#line 2 "src/DataStructure/BIT.hpp"

#include <cassert>
#include <functional>
#line 7 "src/DataStructure/BIT.hpp"

namespace lib {
template <class T>
class BIT {
   public:
    BIT(int N) : _N(N), _bit(_N) {}
    void add(int idx, T value) {
        assert(0 <= idx && idx < _N);
        idx++;
        while (idx <= _N) {
            _bit[idx - 1] += value;
            idx += idx & -idx;
        }
    }

    T sum(int idx) {
        assert(0 <= idx && idx <= _N);
        T value = 0;
        while (idx > 0) {
            value += _bit[idx - 1];
            idx -= idx & -idx;
        }
        return value;
    }

    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= _N);
        return sum(r) - sum(l);
    }

   private:
    int _N;
    std::vector<T> _bit;
};
}  // namespace lib
#line 7 "test/DataStructure/BIT_Point_Add_Range_Sum.test.cpp"

int main() {
    int N, Q;
    std::cin >> N >> Q;

    std::vector<long long> A(N);
    lib::BIT<long long> bit(N);
    for (int i = 0; i < N; i++) {
        std::cin >> A[i];
        bit.add(i, A[i]);
    }

    for (int i = 0; i < Q; i++) {
        long long t, l, r;
        std::cin >> t >> l >> r;
        if (t == 0) {
            bit.add(l, r);
        }
        if (t == 1) {
            std::cout << bit.sum(l, r) << '\n';
        }
    }
}

Back to top page