src/structure/fen2d.hpp

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

Depends on

• src/structure/fenwick_tree.hpp
• src/template.hpp

Verified with

• src/test/yosupo_point_add_rectangle_sum.fen.cpp

Code

#include "fenwick_tree.hpp"

template<typename K,typename T>
struct Fen2D {
    int n;
    vector<pair<K,K>> ps;
    vector<K> xz;
    vector<vector<K>> ys;
    vector<fenwick_tree<T>> bit;

    void add_point(K x,K y){
        ps.emplace_back(x,y);
    }
    void build(){
        xz.resize(si(ps));
        rep(i,si(ps)) xz[i]=ps[i].fi;
        sort(all(xz));
        xz.erase(unique(all(xz)),xz.end());
        n=si(xz);
        bit.resize(n+1);
        ys.resize(n+1);
        sort(all(ps));
        for(int i=0,j=0;i<n;i++) for(;j<si(ps)&&ps[j].fi<=xz[i];ps[j++].fi=i);
        for(auto &[x,y]: ps) for(int i=x+1;i<=n;i+=i& -i) ys[i].push_back(y);
        for(int i=1;i<=n;i++){
            sort(all(ys[i]));
            ys[i].erase(unique(all(ys[i])),ys[i].end());
            bit[i]=fenwick_tree<T>(si(ys[i]));
        }
    }
    void add(K x,K y,T w){
        x=lower_bound(all(xz),x)-xz.begin();
        for(int i=x+1;i<=n;i+=i& -i){
            int j=lower_bound(all(ys[i]),y)-ys[i].begin();
            bit[i].add(j,w);
        }
    }
    T sum(K x,K y){
        x=lower_bound(all(xz),x)-xz.begin();
        T s=0;
        for(;x;x-=x& -x){
            int j=lower_bound(ys[x].begin(),ys[x].end(),y)-ys[x].begin();
            s+=bit[x].sum(j);
        }
        return s;
    }
    T sum(K l,K r,K d,K u){
        return sum(r,u)-sum(l,u)-sum(r,d)+sum(l,d);
    }
};

#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;
    }
};
#line 2 "src/structure/fen2d.hpp"

template<typename K,typename T>
struct Fen2D {
    int n;
    vector<pair<K,K>> ps;
    vector<K> xz;
    vector<vector<K>> ys;
    vector<fenwick_tree<T>> bit;

    void add_point(K x,K y){
        ps.emplace_back(x,y);
    }
    void build(){
        xz.resize(si(ps));
        rep(i,si(ps)) xz[i]=ps[i].fi;
        sort(all(xz));
        xz.erase(unique(all(xz)),xz.end());
        n=si(xz);
        bit.resize(n+1);
        ys.resize(n+1);
        sort(all(ps));
        for(int i=0,j=0;i<n;i++) for(;j<si(ps)&&ps[j].fi<=xz[i];ps[j++].fi=i);
        for(auto &[x,y]: ps) for(int i=x+1;i<=n;i+=i& -i) ys[i].push_back(y);
        for(int i=1;i<=n;i++){
            sort(all(ys[i]));
            ys[i].erase(unique(all(ys[i])),ys[i].end());
            bit[i]=fenwick_tree<T>(si(ys[i]));
        }
    }
    void add(K x,K y,T w){
        x=lower_bound(all(xz),x)-xz.begin();
        for(int i=x+1;i<=n;i+=i& -i){
            int j=lower_bound(all(ys[i]),y)-ys[i].begin();
            bit[i].add(j,w);
        }
    }
    T sum(K x,K y){
        x=lower_bound(all(xz),x)-xz.begin();
        T s=0;
        for(;x;x-=x& -x){
            int j=lower_bound(ys[x].begin(),ys[x].end(),y)-ys[x].begin();
            s+=bit[x].sum(j);
        }
        return s;
    }
    T sum(K l,K r,K d,K u){
        return sum(r,u)-sum(l,u)-sum(r,d)+sum(l,d);
    }
};

Back to top page