Binary Indexed Tree
(DataStructure/bit.hpp)

• View this file on GitHub
• Last update: 2022-10-24 03:26:33+09:00
• Include: #include "DataStructure/bit.hpp"

Required by

• 2D Binary Indexed Tree (DataStructure/2dbit.hpp)
• Static Rectangle Add Rectangle Sum (DataStructure/staticrectaddrectsum.hpp)
• Static Rectangle Sum (DataStructure/staticrectsum.hpp)
• Prefix Substring LCS (String/prefixsubstrlcs.hpp)

Verified with

• Verify/LC_point_add_range_sum.test.cpp
• Verify/LC_prefix_substring_lcs.test.cpp
• Verify/LC_static_range_inversions_query.test.cpp
• Verify/LC_static_range_sum.test.cpp
• Verify/LC_static_rectangle_add_rectangle_sum.test.cpp
• Verify/LC_vertex_add_path_sum.test.cpp
• Verify/LC_vertex_add_range_contour_sum_on_tree.test.cpp

Code

#pragma once

template<typename T>struct BIT{
    int n; T all=0; vector<T> val;
    BIT(int _n=0):n(_n),val(_n+10){}
    void clear(){val.assign(n+10,0); all=T();}
    void add(int i,T x){
        for(i++;i<=n;i+=(i&-i))val[i]=val[i]+x;
        all+=x;
    }
    T sum(int i){
        T res=0;
        for(;i;i-=(i&-i))res+=val[i];
        return res;
    }
    T sum(int L,int R){return sum(R)-sum(L);} // [L,R)

    int lower_bound(T x){
        int ret=0,len=1;
        while(2*len<=n)len<<=1;
        for(;len>=1;len>>=1){
            if(ret+len<=n and val[ret+len]<x){
                ret+=len;
                x-=val[ret];
            }
        }
        return ret;
    }
};

/**
 * @brief Binary Indexed Tree
 */

#line 2 "DataStructure/bit.hpp"

template<typename T>struct BIT{
    int n; T all=0; vector<T> val;
    BIT(int _n=0):n(_n),val(_n+10){}
    void clear(){val.assign(n+10,0); all=T();}
    void add(int i,T x){
        for(i++;i<=n;i+=(i&-i))val[i]=val[i]+x;
        all+=x;
    }
    T sum(int i){
        T res=0;
        for(;i;i-=(i&-i))res+=val[i];
        return res;
    }
    T sum(int L,int R){return sum(R)-sum(L);} // [L,R)

    int lower_bound(T x){
        int ret=0,len=1;
        while(2*len<=n)len<<=1;
        for(;len>=1;len>>=1){
            if(ret+len<=n and val[ret+len]<x){
                ret+=len;
                x-=val[ret];
            }
        }
        return ret;
    }
};

/**
 * @brief Binary Indexed Tree
 */

Back to top page