src/segtree/dynamic_segtree.hpp

• View this file on GitHub
• Last update: 2025-12-30 15:03:15+09:00
• Include: #include "src/segtree/dynamic_segtree.hpp"

Depends on

• src/template.hpp

Verified with

• src/test/yosupo_point_add_range_sum.cpp

Code

#pragma once
#include "../template.hpp"

template<class S,S (*op)(S,S),S (*e)(),typename K=uint64_t> struct dynamic_segtree {
    struct Node {
        Node *p,*left,*right;
        S d;
        Node(Node* _p=nullptr):p(_p),left(nullptr),right(nullptr),d(e()){}
    };

    K n,log;
    Node* root;
    dynamic_segtree(K _n){
        n=__bit_ceil(_n);
        log=__countr_zero(n);
        root=new Node();
    }
    void set(K p,S x){
        Node* now=root;
        for(int i=log;i--;){
            if(p>>i&1){
                if(!now->right) now->right=new Node(now);
                now=now->right;
            }
            else {
                if(!now->left) now->left=new Node(now);
                now=now->left;
            }
        }
        now->d=x;
        while(now->p){
            now=now->p;
            now->d=op(now->left?now->left->d:e(),now->right?now->right->d:e());
        }
    }

    S get(K p){
        Node* now=root;
        for(int i=log;i--;){
            if(p>>i&1){
                if(!now->right) return e();
                now=now->right;
            }
            else {
                if(!now->left) return e();
                now=now->left;
            }
        }
        return now->d;
    }
    S prod(K l,K r){return prod(l,r,root,0,n);}

    S prod(K a,K b,Node*& now,K l,K r){
        if(!now||r<=a||b<=l) return e();
        if(a<=l&&r<=b) return now->d;
        K c=(l+r)>>1;
        S lv=prod(a,b,now->left,l,c);
        S rv=prod(a,b,now->right,c,r);
        return op(lv,rv);
    }
};

template<class T> using DynamicSegtreeFrom=
    dynamic_segtree<class T::S,T::op,T::e,typename T::K>;

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

template<class S,S (*op)(S,S),S (*e)(),typename K=uint64_t> struct dynamic_segtree {
    struct Node {
        Node *p,*left,*right;
        S d;
        Node(Node* _p=nullptr):p(_p),left(nullptr),right(nullptr),d(e()){}
    };

    K n,log;
    Node* root;
    dynamic_segtree(K _n){
        n=__bit_ceil(_n);
        log=__countr_zero(n);
        root=new Node();
    }
    void set(K p,S x){
        Node* now=root;
        for(int i=log;i--;){
            if(p>>i&1){
                if(!now->right) now->right=new Node(now);
                now=now->right;
            }
            else {
                if(!now->left) now->left=new Node(now);
                now=now->left;
            }
        }
        now->d=x;
        while(now->p){
            now=now->p;
            now->d=op(now->left?now->left->d:e(),now->right?now->right->d:e());
        }
    }

    S get(K p){
        Node* now=root;
        for(int i=log;i--;){
            if(p>>i&1){
                if(!now->right) return e();
                now=now->right;
            }
            else {
                if(!now->left) return e();
                now=now->left;
            }
        }
        return now->d;
    }
    S prod(K l,K r){return prod(l,r,root,0,n);}

    S prod(K a,K b,Node*& now,K l,K r){
        if(!now||r<=a||b<=l) return e();
        if(a<=l&&r<=b) return now->d;
        K c=(l+r)>>1;
        S lv=prod(a,b,now->left,l,c);
        S rv=prod(a,b,now->right,c,r);
        return op(lv,rv);
    }
};

template<class T> using DynamicSegtreeFrom=
    dynamic_segtree<class T::S,T::op,T::e,typename T::K>;

Back to top page