src/fenwick_tree.hpp

View this file on GitHub
Last update: 2025-10-07 04:08:36+09:00
Include: #include "src/fenwick_tree.hpp"

Depends on

src/template.hpp

Verified with

src/test/aoj_DSL_2_B.cpp

Code

#pragma once
#include "template.hpp"

template<class T> struct fenwick_tree {
    vector<T> a;
    fenwick_tree(): a(1) {}
    fenwick_tree(int n): a(n + 1) {}
    void add(int i, T x) {
        i++;
        while(i < si(a)) a[i] += x, i += i & -i;
    }
    T sum(int r) {
        T s = 0;
        while(r) s += a[r], r -= r & -r;
        return s;
    }
    T sum(int l, int r) { return sum(r) - sum(l); }

    //sum(0,x+1)がw以上になるような最小のxを返す(各要素は正の数)
    int lower_bound(T w) {
        if(w <= 0) return 0;
        int x = 0, N = si(a) - 1;
        for(int k = 1 << __lg(N); k >>= 1;) {
            if(x + k <= N - 1 && a[x + k] < w) {
                w -= a[x + k];
                x += k;
            }
        }
        return x;
    }
};

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rep(i, n) for(long i = 0; i < (long)(n); ++i)
template<typename T> bool chmin(T& a, T b) { return b < a ? (a = b, 1) : 0; }
template<typename T> bool chmax(T& a, T b) { return b > a ? (a = b, 1) : 0; }
struct _ {
    _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0), cout << fixed << setprecision(16); }
} __;
#line 3 "src/fenwick_tree.hpp"

template<class T> struct fenwick_tree {
    vector<T> a;
    fenwick_tree(): a(1) {}
    fenwick_tree(int n): a(n + 1) {}
    void add(int i, T x) {
        i++;
        while(i < si(a)) a[i] += x, i += i & -i;
    }
    T sum(int r) {
        T s = 0;
        while(r) s += a[r], r -= r & -r;
        return s;
    }
    T sum(int l, int r) { return sum(r) - sum(l); }

    //sum(0,x+1)がw以上になるような最小のxを返す(各要素は正の数)
    int lower_bound(T w) {
        if(w <= 0) return 0;
        int x = 0, N = si(a) - 1;
        for(int k = 1 << __lg(N); k >>= 1;) {
            if(x + k <= N - 1 && a[x + k] < w) {
                w -= a[x + k];
                x += k;
            }
        }
        return x;
    }
};