library

This documentation is automatically generated by online-judge-tools/verification-helper

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

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

Depends on

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) {
        i = clamp(i, 0, n);
        T res = 0;
        for (; i; i -= (i & -i))
            res += val[i];
        return res;
    }
    // [L,R)

    T sum(int L, int R) {
        if (L > R)
            return T(0);
        return sum(R) - sum(L);
    }
    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