---
tags: codebook
---

# segment tree

## basic

constexpr int maxn=2e5+5;
ll arr[(maxn+1)<<2];
 
#define m ((l+r)>>1)
void build(V<int>& v,int i=1,int l=0,int r=maxn){
    if((int)v.size()<=l) return;
    if(r-l==1){arr[i]=v[l];return;}
    
    build(v,i<<1,l,m),build(v,i<<1|1,m,r);
 
    arr[i]=min(arr[i<<1],arr[i<<1|1]);
}
 
void modify(int k,int u,int i=1,int l=0,int r=maxn){
    if(k<l||r<=k) return;
    if(r-l==1){arr[i]=u;return;}
 
    modify(k,u,i<<1,l,m),modify(k,u,i<<1|1,m,r);
    
    arr[i]=min(arr[i<<1],arr[i<<1|1]);
}
 
ll query(int ql,int qr,int i=1,int l=0,int r=maxn){
    if(qr<=l||r<=ql) return LINF;
    if(ql<=l&&r<=qr) return arr[i];
 
    return min(query(ql,qr,i<<1,l,m),query(ql,qr,i<<1|1,m,r));
}
 
 
static inline void solve(){
    int n,q;cin>>n>>q;
    V<int> v(n);
    for(auto& i:v)
        cin>>i;
    build(v);
    while(q--){
        int op;cin>>op;
        switch(op){
            case 1:{
                int k,u;cin>>k>>u,k--;
                modify(k,u);
            }break;    
            case 2:{
                int a,b;cin>>a>>b,a--;
                cout<<query(a,b)<<endl;
            }break;
        }
    }
}

## with lazy propagation

constexpr int maxn=2e5+5;
ll arr[(maxn+1)<<2],set[(maxn+1)<<2],inc[(maxn+1)<<2];
 
#define m ((l+r)>>1)
void push(int i,int l,int r){
    if(r-l==1) return;
    if(set[i]){
        arr[i]=(r-l)*set[i];
        set[i<<1]=set[i<<1|1]=set[i];
        inc[i<<1]=inc[i<<1|1]=0;
        set[i]=0;
    }
    if(inc[i]){
        arr[i]+=(r-l)*inc[i];
        inc[i<<1]+=inc[i];
        inc[i<<1|1]+=inc[i];
        inc[i]=0;
    }
}
void pull(int i,int l,int r){
    if(r-l==1) return;
    arr[i]=0;
    if(set[i<<1])
        arr[i]+=set[i<<1]*(m-l);
    else
        arr[i]+=arr[i<<1];
    arr[i]+=inc[i<<1]*(m-l);
 
    if(set[i<<1|1])
        arr[i]+=set[i<<1|1]*(r-m);
    else
        arr[i]+=arr[i<<1|1];
    arr[i]+=inc[i<<1|1]*(r-m);
}
 
void build(V<int>& v,int i=1,int l=0,int r=maxn){
    if((int)v.size()<=l) return;
    if(r-l==1){arr[i]=v[l];return;}
    
    build(v,i<<1,l,m),build(v,i<<1|1,m,r);
 
    pull(i,l,r);
}
 
void increase(int ql,int qr,int x,int i=1,int l=0,int r=maxn){
    if(qr<=l||r<=ql) return;
    if(ql<=l&&r<=qr){
        inc[i]+=x;
        return;
    }
 
    push(i,l,r);
 
    increase(ql,qr,x,i<<1,l,m),increase(ql,qr,x,i<<1|1,m,r);
 
    pull(i,l,r);
}
 
void modify(int ql,int qr,int x,int i=1,int l=0,int r=maxn){
    if(qr<=l||r<=ql) return;
    if(ql<=l&&r<=qr){
        set[i]=x,inc[i]=0;
        return;
    }
 
    push(i,l,r);
 
    modify(ql,qr,x,i<<1,l,m),modify(ql,qr,x,i<<1|1,m,r);
 
    pull(i,l,r);
}
 
ll query(int ql,int qr,int i=1,int l=0,int r=maxn){
    if(qr<=l||r<=ql) return 0;
    if(ql<=l&&r<=qr){ 
        ll ret=arr[i];
        if(set[i])
            ret=set[i]*(r-l);
        ret+=inc[i]*(r-l);
        return ret;
    }
    push(i,l,r);
 
    return query(ql,qr,i<<1,l,m)+query(ql,qr,i<<1|1,m,r);
}
#undef m

## with persistency

constexpr int maxn=2e5+5;
 
 
struct node{
    ll val;
    node *l,*r;
 
    node(ll x=0):val(x){
        l=r=nullptr;
    }
    void pull(){
        val=0;
        for(auto i:{l,r})
            if(i) val+=i->val;
    }
};
 
 
 
#define m ((l+r)>>1)
 
node* build(V<int>& v,int l=0,int r=maxn){
    if((int)v.size()<=l) return nullptr;
    if(r-l==1) return new node(v[l]);
    
    node *ret=new node;
    ret->l=build(v,l,m);
    ret->r=build(v,m,r);
    
    ret->pull();
    return ret;
}
 
node* modify(node* rt,int k,int x,int l=0,int r=maxn){
    if(k<l||r<=k) return rt;
    if(r-l==1) return new node(x);
 
    node* ret=new node;
    ret->l=modify(rt->l,k,x,l,m);
    ret->r=modify(rt->r,k,x,m,r);
 
    ret->pull();
    return ret;
}
 
ll query(node* rt,int ql,int qr,int l=0,int r=maxn){
    if(qr<=l||r<=ql||!rt) return 0;
    if(ql<=l&&r<=qr) return rt->val;
 
    return query(rt->l,ql,qr,l,m)+query(rt->r,ql,qr,m,r);
}
 
#undef m
 
#define endl '\n'
static inline void solve(){
    int n,q;cin>>n>>q;
    V<int> v(n);
    for(auto& i:v)
        cin>>i;
    V<node*> root{build(v)};
    while(q--){
        int op;cin>>op;
        switch(op){
            case 1:{
                int k,a,x;cin>>k>>a>>x,k--,a--;
                root[k]=modify(root[k],a,x);
            }break;
            case 2:{
                int k,a,b;cin>>k>>a>>b,k--,a--;
                cout<<query(root[k],a,b)<<endl;
            }break;
            case 3:{
                int k;cin>>k,k--;
                root.push_back(root[k]);     
            }break;
        }
    }
}

## old ver don't see

#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<limits>
#include<cmath>
using namespace std;
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v){
    for(const auto& i:v) os<<i<<' ';
    return os;
}

template<typename T>
struct segment_tree{
    const T limit;
    const size_t _size;
    vector<T> vec;
    const T& (*cmp)(const T&,const T&);
    const T operator()(size_t l,size_t r){
        if(l==r) return limit;
        if(l>r) swap(l,r);
        l+=_size,r+=_size;
        T ans=limit;
        while(l<r){
            if(l&1) ans=cmp(ans,vec[l++]);
            if(r&1) ans=cmp(ans,vec[--r]);
            l>>=1,r>>=1;
        }
        return ans;
    }
    void update(size_t pos,T x){
        pos+=_size,vec[pos]=x;
        while(pos!=1)vec[pos>>1]=cmp(vec[pos>>1],vec[pos]),pos>>=1;
    }
    segment_tree(const vector<T>& v,const T& (*c)(const T&,const T&)=
    [](const auto& a,const auto& b)->const decltype(a){return (a<b?a:b);}):
    limit((c(numeric_limits<T>::min(),numeric_limits<T>::max())==
    numeric_limits<T>::min()?numeric_limits<T>::max():numeric_limits<T>::min())),
    _size(v.size()),vec(_size<<1),cmp(c){
        for(size_t i=0;i!=_size;i++)
            vec[_size+i]=v[i];
        for(size_t i=_size-1;i;i--)
            vec[i]=cmp(vec[i<<1],vec[(i<<1)+1]);
    }
};
int main(){
	vector<int> vec{1,2,4,6,3,2,8,7,9,0};
	segment_tree<int> mintree(vec,[](const auto& a,const auto& b)->decltype(a){return (a<b?a:b);});
	segment_tree<int> maxtree(vec,[](const auto& a,const auto& b)->decltype(a){return (a>b?a:b);});
	cout<<mintree(1,10)<<endl;
	cout<<maxtree(1,10)<<endl;
	maxtree.update(5,20);
	cout<<maxtree.vec<<endl;
	cout<<maxtree(1,10)<<endl;
	return 0;
}

## another version

template<typename T>
struct segment_tree{
#define left(x) (x<<1)
#define right(x) ((x<<1)+1)
#define parent(x) (x>>1)
	T (*cmp)(T,T);
	vector<T> vec;const size_t _size;
	const T operator[](size_t pos){return vec[pos+_size];}
	T operator()(size_t l,size_t r){
		if(l>r) swap(l,r);
		l+=_size,r+=_size;
		T ans=vec[l];
		while(l<r){
			if(l&1) ans=cmp(ans,vec[l++]);
			if(r&1) ans=cmp(ans,vec[--r]);
			l=parent(l),r=parent(r);
		}
		return ans;
	}
	void update(size_t pos,T x){
		pos+=_size;
		vec[pos]=x;
		while(pos!=1){vec[parent(pos)]=cmp(vec[parent(pos)],vec[pos]);pos=parent(pos);}
	}
	segment_tree(const vector<T>& v,T (*c)(T,T)=[](auto a,auto b){return (a<b?a:b);}):cmp(c),vec(v.size()<<1,0),_size(v.size()){
		for(size_t t=_size;t!=(_size<<1);t++)
			vec[t]=v[t-_size];
		for(size_t t=_size-1;t;t--)
			vec[t]=cmp(vec[left(t)],vec[right(t)]);
	}
#undef left
#undef right
#undef parent
};
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v){
	for(const auto& i:v) os<<i<<' ';
	return os;
}

## third version

#include<iostream>
#include<vector>
#include<algorithm>
#include<limits>
using namespace std;
int lookup_popcnt(unsigned int n) {
# define BIT2(n) n      , n+1      , n+1      , n+2
# define BIT4(n) BIT2(n), BIT2(n+1), BIT2(n+1), BIT2(n+2)
# define BIT6(n) BIT4(n), BIT4(n+1), BIT4(n+1), BIT4(n+2)
# define BIT8(n) BIT6(n), BIT6(n+1), BIT6(n+1), BIT6(n+2)
	static constexpr unsigned char TABLE[256] = {BIT8(0)};
	return TABLE[n       & 0xff] +
	       TABLE[(n >> 8)  & 0xff] +
	       TABLE[(n >> 16) & 0xff] +
	       TABLE[(n >> 24) & 0xff];
}
inline size_t lchild(const size_t& n) {return n << 1;}
inline size_t rchild(const size_t& n) {return n << 1 | 1;}
inline size_t parent(const size_t& n) {return n >> 1;}
inline size_t sibling(const size_t& n) {return n ^ 1;}
struct segment_tree {
	const size_t size, height;
	vector<int> data, lazy;
	void apply(size_t pos, int val) {
		data[pos] += val;
		if (pos < size) lazy[pos] += val;
	}
	void push(int pos) {
		for (int s = height; s > 0; --s) {
			int i = pos >> s;
			if (lazy[i] != 0) {
				apply(lchild(i), lazy[i]);
				apply(rchild(i), lazy[i]);
				lazy[i] = 0;
			}
		}
	}
	int operator()(size_t l, size_t r) {
		int res = numeric_limits<int>::min();
		l += size, r += size;
		push(l), push(r - 1);
		for (; l < r; l >>= 1, r >>= 1) {
			if (l & 1) res = max(res, data[l++]);
			if (r & 1) res = max(res, data[--r]);
		}
		return res;
	}
	void build(size_t pos) {
		while (pos > 1)
			pos >>= 1, data[pos] = max(data[lchild(pos)], data[rchild(pos)]) + lazy[pos];
	}
	void increase(size_t l, size_t r, int val) {
		int l0 = l += size, r0 = r += size;
		for (; l < r; l >>= 1, r >>= 1) {
			if (l & 1) apply(l++, val);
			if (r & 1) apply(--r, val);
		}
		build(l0), build(r0 - 1);
	}
	void modify(size_t pos, int val) {
		for (data[pos += size] = val; pos > 1; pos >>= 1)
			data[parent(pos)] = max(data[pos], data[sibling(pos)]);
	}
	void init() {
		for (int i = size - 1; i > 0; --i)
			data[i] = max(data[lchild(i)], data[rchild(i)]);
	}
	segment_tree(const vector<int>& v):
		size(v.size()), height(lookup_popcnt(size)), data(2 * v.size()), lazy(size) {
		for (size_t i = 0; i != size; i++)
			data[i + size] = v[i];
		init();
	}
};
int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n, m, c; cin >> n >> m;
	vector<int> vec(n, 0);
	segment_tree tree(vec);
	size_t a, b;
	for (int i = 0; i != m; i++)
		cin >> a >> b >> c, tree.increase(a - 1, b, c);
	cout << tree(0, n);
	return 0;
}

## v4

#include<iostream>
#include<vector>
#include<algorithm>
#include<limits>
#define endl '\n'
using namespace std;
int lookup_popcnt(unsigned int n) {
# define BIT2(n) n      , n+1      , n+1      , n+2
# define BIT4(n) BIT2(n), BIT2(n+1), BIT2(n+1), BIT2(n+2)
# define BIT6(n) BIT4(n), BIT4(n+1), BIT4(n+1), BIT4(n+2)
# define BIT8(n) BIT6(n), BIT6(n+1), BIT6(n+1), BIT6(n+2)
	static constexpr unsigned char TABLE[256] = {BIT8(0)};
	return TABLE[n       & 0xff] +
	       TABLE[(n >> 8)  & 0xff] +
	       TABLE[(n >> 16) & 0xff] +
	       TABLE[(n >> 24) & 0xff];
}
inline size_t lchild(const size_t& n) {return n << 1;}
inline size_t rchild(const size_t& n) {return n << 1 | 1;}
inline size_t parent(const size_t& n) {return n >> 1;}
inline size_t sibling(const size_t& n) {return n ^ 1;}
template<class cmp = less<int>>
struct segment_tree {
	const size_t size, height;
	const int limit;
	vector<int> data, lazy;
	int max(const int& a, const int& b) {
		return cmp()(a, b) ? b : a;
	}
	void apply(size_t pos, int val) {
		data[pos] += val;
		if (pos < size) lazy[pos] += val;
	}
	void push(int pos) {
		for (int s = height; s > 0; --s) {
			int i = pos >> s;
			if (lazy[i] != 0) {
				apply(lchild(i), lazy[i]);
				apply(rchild(i), lazy[i]);
				lazy[i] = 0;
			}
		}
	}
	int operator()(size_t l, size_t r) {
		int res = limit;
		l += size, r += size;
		push(l), push(r - 1);
		for (; l < r; l >>= 1, r >>= 1) {
			if (l & 1) res = max(res, data[l++]);
			if (r & 1) res = max(res, data[--r]);
		}
		return res;
	}
	void build(size_t pos) {
		while (pos > 1)
			pos >>= 1, data[pos] = max(data[lchild(pos)], data[rchild(pos)]) + lazy[pos];
	}
	void increase(size_t l, size_t r, int val) {
		int l0 = l += size, r0 = r += size;
		for (; l < r; l >>= 1, r >>= 1) {
			if (l & 1) apply(l++, val);
			if (r & 1) apply(--r, val);
		}
		build(l0), build(r0 - 1);
	}
	void modify(size_t pos, int val) {
		for (data[pos += size] = val; pos > 1; pos >>= 1)
			data[parent(pos)] = max(data[pos], data[sibling(pos)]);
	}
	void init() {
		for (int i = size - 1; i > 0; --i)
			data[i] = max(data[lchild(i)], data[rchild(i)]);
	}
	segment_tree(const vector<int>& v):
		size(v.size()), height(lookup_popcnt(size)),
		limit(cmp()(numeric_limits<int>::min(), numeric_limits<int>::max()) ?
		      numeric_limits<int>::min() : numeric_limits<int>::max()),
		data(2 * v.size()), lazy(size) {
		for (size_t i = 0; i != size; i++)
			data[i + size] = v[i];
		init();
	}
};
ostream& operator<<(ostream& os, vector<auto>& v) {
	for (auto& i : v)
		cout << i << ' ';
	return os;
}
int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n, l, r; cin >> n;
	vector<int> v(n);
	for (auto& i : v) cin >> i;
	segment_tree<less<int>> mintree(v);
	segment_tree<greater<int>> maxtree(v);
	while (cin >> l >> r)
		cout << mintree(l - 1, r) + maxtree(l - 1, r) << endl;
	return 0;
}

## recursive ver

#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
#include<functional>
#define endl '\n'
using namespace std;
int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n, a, b; cin >> n;
	vector<pair<int, int>> seg(n << 2, {INT_MIN, INT_MAX});
	auto pull = [](auto a, auto b) -> pair<int, int> {
		return {max(a.first, b.first), min(a.second, b.second)};
	};
	auto lch = [](int x) {return (x << 1) + 1;};
	auto rch = [](int x) {return (x << 1) + 2;};
	auto modify = [&](int i, int x) {
		function<void(int, int, int)> _ = [&](int id, int l, int r) {
			if (l == r) {seg[id] = {x, x}; return;}
			int m = (long long)(l + r) >> 1;
			if (i <= m)
				_(lch(id), l, m);
			else
				_(rch(id), m + 1, r);
			seg[id] = pull(seg[lch(id)], seg[rch(id)]);
		}; _(0, 0, n - 1);
	};
	auto query = [&](int ql, int qr) {
		function<pair<int, int>(int, int, int)> _ = [&](int id, int l, int r) -> pair<int, int> {
			if (qr < l || r < ql) return {INT_MIN, INT_MAX};
			if (ql <= l && r <= qr) return seg[id];
			int m = (long long)(l + r) >> 1;
			return pull(_(lch(id), l, m), _(rch(id), m + 1, r));
		}; return _(0, 0, n - 1);
	};
	for (int i = 0, tmp; i != n; i++)
		cin >> tmp, modify(i, tmp);
	while (cin >> a >> b) {
		int p, q; tie(p, q) = query(a - 1, b - 1);
		cout << p + q << endl;
	}
	return 0;
}