data_structure/fenwick_tree.hpp

• View this file on GitHub
• Last update: 2025-02-27 06:13:46+09:00
• Include: #include "data_structure/fenwick_tree.hpp"

Required by

• math/inversion_number.hpp

Verified with

• verify/aoj/aoj_alds1_5_d.test.cpp
• verify/yosupo/yosupo_point_add_range_sum_fenwick.test.cpp

Code

template <typename T=int>
struct FenwickTree {
    int n;
    vector<T> data;
    FenwickTree(int n) : n(n), data(n, 0) {}

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

    T sum(int r) {
        T s = 0;
        for(; r; r -= r & -r) s += data[r - 1];
        return s;
    }
    
    T sum(int l, int r) {
        return sum(r) - sum(l);
    }
};

#line 1 "data_structure/fenwick_tree.hpp"
template <typename T=int>
struct FenwickTree {
    int n;
    vector<T> data;
    FenwickTree(int n) : n(n), data(n, 0) {}

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

    T sum(int r) {
        T s = 0;
        for(; r; r -= r & -r) s += data[r - 1];
        return s;
    }
    
    T sum(int l, int r) {
        return sum(r) - sum(l);
    }
};

Back to top page