src/segtree/segtree2d.hpp

• View this file on GitHub
• Last update: 2026-02-20 08:22:15+09:00
• Include: #include "src/segtree/segtree2d.hpp"

Depends on

• src/segtree/segtree.hpp
• src/template.hpp

Verified with

• src/test/yosupo_point_add_rectangle_sum.cpp
• src/test/yuki_3330.cpp

Code

#pragma once
#include "segtree.hpp"

template<typename K,class S,S (*op)(S,S),S (*e)()> struct segtree_2d {
    int n;
    vector<segtree<S,op,e>> d;
    vector<K> xs;
    vector<vector<K>> ys;
    vector<pair<K,K>> xp;
    vector<vector<pair<K,K>>> yp;
    segtree_2d(){}
    void add_point(K x,K y){xp.push_back({x,y});}

    void build(){
        sort(all(xp));
        xp.erase(unique(all(xp)),xp.end());
        n=__bit_ceil(xp.size());
        for(auto [x,y]:xp) xs.push_back(x);
        yp.resize(2*n);
        ys.resize(2*n);
        rep(i,si(xp)){
            yp[n+i]={make_pair(xp[i].se,xp[i].fi)};
            ys[n+i]={xp[i].se};
        }
        for(int i=n;--i;){
            merge(all(yp[i*2]),all(yp[i*2+1]),back_inserter(yp[i]));
            merge(all(ys[i*2]),all(ys[i*2+1]),back_inserter(ys[i]));
        }
        d.resize(2*n);
        for(int i=1;i<2*n;i++){
            d[i]=segtree<S,op,e>(si(yp[i]));
        }
    }

    void set(K x,K y,S v){
        auto it=lower_bound(all(xp),make_pair(x,y));
        assert(it!=xp.end()&&it->fi==x&&it->se==y);
        int k=it-xp.begin();
        for(k+=n;k;k>>=1){
            auto it2=lower_bound(all(yp[k]),make_pair(y,x));
            assert(it2!=yp[k].end());
            int id=it2-yp[k].begin();
            d[k].set(id,v);
        }
    }
    S get(K x,K y){
        auto it=lower_bound(all(xp),make_pair(x,y));
        assert(it!=xp.end()&&it->fi==x&&it->se==y);
        int k=it-xp.begin();
        k+=n;
        auto it2=lower_bound(all(yp[k]),make_pair(y,x));
        assert(it2!=yp[k].end());
        int id=it2-yp[k].begin();
        return d[k].get(id);
    }
    void apply(K x,K y,S v){
        set(x,y,op(get(x,y),v));
    }

    S range(K lv,K rv,K dv,K uv){
        if(dv>=uv) return e();
        int l=lower_bound(all(xs),lv)-xs.begin();
        int r=lower_bound(all(xs),rv)-xs.begin();
        S sml=e(),smr=e();
        for(l+=n,r+=n;l<r;l>>=1,r>>=1){
            if(l&1){
                int li=lower_bound(all(ys[l]),dv)-ys[l].begin();
                int ri=lower_bound(all(ys[l]),uv)-ys[l].begin();
                sml=op(sml,d[l].prod(li,ri));
                l++;
            }
            if(r&1){
                --r;
                int li=lower_bound(all(ys[r]),dv)-ys[r].begin();
                int ri=lower_bound(all(ys[r]),uv)-ys[r].begin();
                smr=op(d[r].prod(li,ri),smr);
            }
        }
        return op(sml,smr);
    }
};

#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/segtree/segtree.hpp"

template<class S,S (*op)(S,S),S (*e)()> struct segtree {
    int n;
    vector<S> d;
    segtree():segtree(1){}
    explicit segtree(int n_):segtree(vector<S>(n_,e())){}
    explicit segtree(const vector<S>& a):n(__bit_ceil(a.size())),d(n*2,e()){
        rep(i,si(a)) d[n+i]=a[i];
        for(int i=n;--i;) d[i]=op(d[i*2],d[i*2+1]);
    }
    void set(int i,S x){
        for(d[i+=n]=x;i>>=1;) d[i]=op(d[i*2],d[i*2+1]);
    }
    S get(int i){return d[i+n];}
    S prod(int l,int r){
        S L=e(),R=e();
        for(l+=n,r+=n;l<r;l>>=1,r>>=1){
            if(l&1) L=op(L,d[l++]);
            if(r&1) R=op(d[--r],R);
        }
        return op(L,R);
    }
    template<typename F> int max_right(int l,F f) const {
        if(l==n) return n;
        l+=n;
        S sm=e();
        do {
            while(~l&1) l>>=1;
            if(!f(op(sm,d[l]))){
                while(l<n){
                    l<<=1;
                    if(f(op(sm,d[l]))) sm=op(sm,d[l++]);
                }
                return l-n;
            }
            sm=op(sm,d[l++]);
        } while((l& -l)!=l);
        return n;
    }
    template<typename F> int min_left(int r,F f) const {
        if(!r) return 0;
        r+=n;
        S sm=e();
        do {
            r--;
            while(r>1 and r&1) r>>=1;
            if(!f(op(d[r],sm))){
                while(r<n){
                    r=(2*r+1);
                    if(f(op(d[r],sm))) sm=op(d[r--],sm);
                }
                return r+1-n;
            }
            sm=op(d[r],sm);
        } while((r& -r)!=r);
        return 0;
    }
};

template<class T> using SegtreeFrom=segtree<typename T::S,T::op,T::e>;
#line 3 "src/segtree/segtree2d.hpp"

template<typename K,class S,S (*op)(S,S),S (*e)()> struct segtree_2d {
    int n;
    vector<segtree<S,op,e>> d;
    vector<K> xs;
    vector<vector<K>> ys;
    vector<pair<K,K>> xp;
    vector<vector<pair<K,K>>> yp;
    segtree_2d(){}
    void add_point(K x,K y){xp.push_back({x,y});}

    void build(){
        sort(all(xp));
        xp.erase(unique(all(xp)),xp.end());
        n=__bit_ceil(xp.size());
        for(auto [x,y]:xp) xs.push_back(x);
        yp.resize(2*n);
        ys.resize(2*n);
        rep(i,si(xp)){
            yp[n+i]={make_pair(xp[i].se,xp[i].fi)};
            ys[n+i]={xp[i].se};
        }
        for(int i=n;--i;){
            merge(all(yp[i*2]),all(yp[i*2+1]),back_inserter(yp[i]));
            merge(all(ys[i*2]),all(ys[i*2+1]),back_inserter(ys[i]));
        }
        d.resize(2*n);
        for(int i=1;i<2*n;i++){
            d[i]=segtree<S,op,e>(si(yp[i]));
        }
    }

    void set(K x,K y,S v){
        auto it=lower_bound(all(xp),make_pair(x,y));
        assert(it!=xp.end()&&it->fi==x&&it->se==y);
        int k=it-xp.begin();
        for(k+=n;k;k>>=1){
            auto it2=lower_bound(all(yp[k]),make_pair(y,x));
            assert(it2!=yp[k].end());
            int id=it2-yp[k].begin();
            d[k].set(id,v);
        }
    }
    S get(K x,K y){
        auto it=lower_bound(all(xp),make_pair(x,y));
        assert(it!=xp.end()&&it->fi==x&&it->se==y);
        int k=it-xp.begin();
        k+=n;
        auto it2=lower_bound(all(yp[k]),make_pair(y,x));
        assert(it2!=yp[k].end());
        int id=it2-yp[k].begin();
        return d[k].get(id);
    }
    void apply(K x,K y,S v){
        set(x,y,op(get(x,y),v));
    }

    S range(K lv,K rv,K dv,K uv){
        if(dv>=uv) return e();
        int l=lower_bound(all(xs),lv)-xs.begin();
        int r=lower_bound(all(xs),rv)-xs.begin();
        S sml=e(),smr=e();
        for(l+=n,r+=n;l<r;l>>=1,r>>=1){
            if(l&1){
                int li=lower_bound(all(ys[l]),dv)-ys[l].begin();
                int ri=lower_bound(all(ys[l]),uv)-ys[l].begin();
                sml=op(sml,d[l].prod(li,ri));
                l++;
            }
            if(r&1){
                --r;
                int li=lower_bound(all(ys[r]),dv)-ys[r].begin();
                int ri=lower_bound(all(ys[r]),uv)-ys[r].begin();
                smr=op(d[r].prod(li,ri),smr);
            }
        }
        return op(sml,smr);
    }
};

Back to top page