Library/DataStructure/FenwickTree.hpp

View this file on GitHub
Last update: 2026-06-01 14:08:55+09:00
Include: #include "Library/DataStructure/FenwickTree.hpp"

Depends on

Library/Common.hpp

Verified with

verify/LC-PointAddRangeSum-FenwickTree.test.cpp

Code

#include "../Common.hpp"

template<typename Ordered>
struct FenwickTree{
    public:
    FenwickTree(int N) : size_(N){
        data_.resize(size_ + 1, 0);
    }

    Ordered Sum(int i){
        Ordered ret = 0;
        for(; i > 0; i -= i & -i) ret += data_[i];
        return ret;
    }
    
    Ordered Sum(int l, int r){
        return Sum(r) - Sum(l - 1);
    }

    void Add(int i, Ordered v){
        for(; i <= size_; i += i & -i) data_[i] += v;
    }

    private:
    int size_;
    vector<Ordered> data_;
};

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bit>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 2 "Library/DataStructure/FenwickTree.hpp"

template<typename Ordered>
struct FenwickTree{
    public:
    FenwickTree(int N) : size_(N){
        data_.resize(size_ + 1, 0);
    }

    Ordered Sum(int i){
        Ordered ret = 0;
        for(; i > 0; i -= i & -i) ret += data_[i];
        return ret;
    }
    
    Ordered Sum(int l, int r){
        return Sum(r) - Sum(l - 1);
    }

    void Add(int i, Ordered v){
        for(; i <= size_; i += i & -i) data_[i] += v;
    }

    private:
    int size_;
    vector<Ordered> data_;
};