library/structure/FenwickTree.hpp

• View this file on GitHub
• Last update: 2025-10-31 18:20:20+09:00
• Include: #include "library/structure/FenwickTree.hpp"

Depends on

• library/template/template.hpp

Verified with

• verify/yosupo/point-add-range-sum.test.cpp

Code

#pragma once

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

template <typename T = ll>
struct FenwickTree {
    ll n;
    vec<T> data;

    FenwickTree() = default;
    FenwickTree(ll size) { init(size); }
    FenwickTree(vec<T> &a) {
        init(sz(a));
        rep(i, sz(a)) add(i, a[i]);
    }
    
    void init(ll size) {
        n = size + 2;
        data.assign(n + 1, {});
    }

    // sum of [0, k]
    T sum(ll k) const {
        if (k < 0) return T{};
        T ret{};
        for (++k; k > 0; k -= k & -k) ret += data[k];
        return ret;
    }

    // sum of [l, r]
    inline T sum(ll l, ll r) const { return sum(r) - sum(l - 1); }

    // value of k
    inline T operator[](ll k) const { return sum(k) - sum(k - 1); }

    // data[k] += x
    void add(ll k, T x) {
        for (++k; k < n; k += k & -k) data[k] += x;
    }

    // data[l, ..., r] += x
    void imos(ll l, ll r, T x) {
        add(l, x);
        add(r + 1, -x);
    }
    
    // min i s.t. sum(i) >= w
    ll lower_bound(T w) {
        if (w <= 0) return 0;
        ll x = 0;
        for (ll k = 1 << __lg(n); k; k >>= 1) {
            if (x + k <= n - 1 && data[x + k] < w) {
                w -= data[x + k];
                x += k;
            }
        }
        return x;
    }

    // min i s.t. sum(i) > w
    ll upper_bound(T w) {
        if (w < 0) return 0;
        ll x = 0;
        for (ll k = 1 << __lg(n); k; k >>= 1) {
            if (x + k <= n - 1 && data[x + k] <= w) {
                w -= data[x + k];
                x += k;
            }
        }
        return x;
    }
};

#line 2 "library/structure/FenwickTree.hpp"

#line 2 "library/template/template.hpp"

#include <bits/stdc++.h>
using namespace std;
#define MM << ' ' <<
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using vl = vector<ll>;
template <class T> using vec = vector<T>;
template <class T> using vv = vec<vec<T>>;
template <class T> using vvv = vv<vec<T>>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, r) for(ll i = 0; i < (r); i++)
#define reps(i, l, r) for(ll i = (l); i < (r); i++)
#define rrep(i, l, r) for(ll i = (r) - 1; i >= l; i--)
template <class T> void uniq(T &a) { sort(all(a)); erase(unique(all(a)), a.end()); }
#define all(a) (a).begin(), (a).end()
#define sz(a) (ll)(a).size()
const ll INF = numeric_limits<ll>::max() / 4;
const ld inf = numeric_limits<ld>::max() / 2;
const ll mod1 = 1000000007;
const ll mod2 = 998244353;
const ld pi = 3.141592653589793238;
template <class T> void rev(T &a) { reverse(all(a)); }
ll popcnt(ll a) { return __builtin_popcountll(a); }
template<typename T>
bool chmax(T &a, const T& b) { return a < b ? a = b, true : false; }
template<typename T>
bool chmin(T &a, const T& b) { return a > b ? a = b, true : false; }
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
	os << p.first << " " << p.second;
	return os;
}
template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
	is >> p.first >> p.second;
	return is;
}
template <typename T>
ostream& operator<<(ostream& os, const vec<T>& v) {
	rep(i, sz(v)) {
		os << v[i] << " \n"[i + 1 == sz(v)];
	}
	return os;
}
template <typename T>
istream& operator>>(istream& is, vec<T>& v) {
	for (T& in : v) is >> in;
	return is;
}
void yesno(bool t) {
	cout << (t ? "Yes" : "No") << endl;
}
#line 4 "library/structure/FenwickTree.hpp"

template <typename T = ll>
struct FenwickTree {
    ll n;
    vec<T> data;

    FenwickTree() = default;
    FenwickTree(ll size) { init(size); }
    FenwickTree(vec<T> &a) {
        init(sz(a));
        rep(i, sz(a)) add(i, a[i]);
    }
    
    void init(ll size) {
        n = size + 2;
        data.assign(n + 1, {});
    }

    // sum of [0, k]
    T sum(ll k) const {
        if (k < 0) return T{};
        T ret{};
        for (++k; k > 0; k -= k & -k) ret += data[k];
        return ret;
    }

    // sum of [l, r]
    inline T sum(ll l, ll r) const { return sum(r) - sum(l - 1); }

    // value of k
    inline T operator[](ll k) const { return sum(k) - sum(k - 1); }

    // data[k] += x
    void add(ll k, T x) {
        for (++k; k < n; k += k & -k) data[k] += x;
    }

    // data[l, ..., r] += x
    void imos(ll l, ll r, T x) {
        add(l, x);
        add(r + 1, -x);
    }
    
    // min i s.t. sum(i) >= w
    ll lower_bound(T w) {
        if (w <= 0) return 0;
        ll x = 0;
        for (ll k = 1 << __lg(n); k; k >>= 1) {
            if (x + k <= n - 1 && data[x + k] < w) {
                w -= data[x + k];
                x += k;
            }
        }
        return x;
    }

    // min i s.t. sum(i) > w
    ll upper_bound(T w) {
        if (w < 0) return 0;
        ll x = 0;
        for (ll k = 1 << __lg(n); k; k >>= 1) {
            if (x + k <= n - 1 && data[x + k] <= w) {
                w -= data[x + k];
                x += k;
            }
        }
        return x;
    }
};

Back to top page