src/structure/fenwick_tree.hpp

View this file on GitHub
Last update: 2026-03-17 19:58:42+09:00
Include: #include "src/structure/fenwick_tree.hpp"

Depends on

src/template.hpp

Required by

src/structure/fen2d.hpp

Verified with

Code

#pragma once
#include "../template.hpp"

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

    int lower_bound(T w){
        if(w<=0) return 0;
        int x=0,k=1;
        while(k<si(a))k<<=1;
        for(;k;k>>=1){
            if(x+k<si(a)&&a[x+k]<w){
                w-=a[x+k];
                x+=k;
            }
        }
        return x+1;
    }
};

#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(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 3 "src/structure/fenwick_tree.hpp"

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

    int lower_bound(T w){
        if(w<=0) return 0;
        int x=0,k=1;
        while(k<si(a))k<<=1;
        for(;k;k>>=1){
            if(x+k<si(a)&&a[x+k]<w){
                w-=a[x+k];
                x+=k;
            }
        }
        return x+1;
    }
};