2D Binary Indexed Tree
(DataStructure/2dbit.hpp)

• View this file on GitHub
• Last update: 2023-01-16 20:41:46+09:00
• Include: #include "DataStructure/2dbit.hpp"

Depends on

• Binary Indexed Tree (DataStructure/bit.hpp)

Code

#pragma once
#include "DataStructure/bit.hpp"

template<class T>struct BIT2D{
    int n; vector<BIT<T>> d;
    vector<int> xs; vector<vector<int>> ys;
    vector<pair<ll,ll>> p;
    BIT2D(){}
    void push(ll x,ll y){p.push_back({x,y});}
    void init(){
        rep(i,0,p.size())xs.push_back(p[i].first);
        sort(ALL(xs)); xs.erase(unique(ALL(xs)),xs.end());
        n=xs.size()+1; ys.resize(n);
        rep(j,0,p.size()){
            int s=upper_bound(ALL(xs),p[j].first)-xs.begin();
            for(int i=s;i<n;i+=(i&-i))ys[i].push_back(p[j].second);
        }
        d.resize(n);
        rep(i,0,n){
            sort(ALL(ys[i])); ys[i].erase(unique(ALL(ys[i])),ys[i].end());
            d[i]=BIT<T>(ys[i].size()+2);
        }
    }
    void add(ll x,ll y,T z=1){
        int s=upper_bound(ALL(xs),x)-xs.begin();
        for(int i=s;i<n;i+=(i&-i)){
            int idx=upper_bound(ALL(ys[i]),y)-ys[i].begin();
            d[i].add(idx,z);
        }
    }
    T sum(ll x,ll y){
        T res=0;
        int s=upper_bound(ALL(xs),x)-xs.begin();
        for(int i=s;i;i-=(i&-i)){
            int idx=upper_bound(ALL(ys[i]),y)-ys[i].begin();
            res+=d[i].sum(idx+1);
        }
        return res;
    }
    T sum(ll x1,ll y1,ll x2,ll y2){return sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1);}
};

/**
 * @brief 2D 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
 */
#line 3 "DataStructure/2dbit.hpp"

template<class T>struct BIT2D{
    int n; vector<BIT<T>> d;
    vector<int> xs; vector<vector<int>> ys;
    vector<pair<ll,ll>> p;
    BIT2D(){}
    void push(ll x,ll y){p.push_back({x,y});}
    void init(){
        rep(i,0,p.size())xs.push_back(p[i].first);
        sort(ALL(xs)); xs.erase(unique(ALL(xs)),xs.end());
        n=xs.size()+1; ys.resize(n);
        rep(j,0,p.size()){
            int s=upper_bound(ALL(xs),p[j].first)-xs.begin();
            for(int i=s;i<n;i+=(i&-i))ys[i].push_back(p[j].second);
        }
        d.resize(n);
        rep(i,0,n){
            sort(ALL(ys[i])); ys[i].erase(unique(ALL(ys[i])),ys[i].end());
            d[i]=BIT<T>(ys[i].size()+2);
        }
    }
    void add(ll x,ll y,T z=1){
        int s=upper_bound(ALL(xs),x)-xs.begin();
        for(int i=s;i<n;i+=(i&-i)){
            int idx=upper_bound(ALL(ys[i]),y)-ys[i].begin();
            d[i].add(idx,z);
        }
    }
    T sum(ll x,ll y){
        T res=0;
        int s=upper_bound(ALL(xs),x)-xs.begin();
        for(int i=s;i;i-=(i&-i)){
            int idx=upper_bound(ALL(ys[i]),y)-ys[i].begin();
            res+=d[i].sum(idx+1);
        }
        return res;
    }
    T sum(ll x1,ll y1,ll x2,ll y2){return sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1);}
};

/**
 * @brief 2D Binary Indexed Tree
*/

Back to top page