Segment Tree

「段木」を簡単に整理します.
注意:cp-アルゴリズム。com
セグメントツリー
Segment Treeは、配列の区間クエリーを効率的に行うためのデータ構造です.配列内の任意の値を変更することで、効率的に更新することもできます.たとえば、ペアのクエリーを処理するセグメントツリーです.
construct(build)

メモリ
アレイのサイズはnなので、アクティブにするには4*n個のセルが必要です.
各ノードには最大2つのサブノードがあり、ツリーの高さはlog(n)である.
したがって,1+2+4+⋯+2‐log 2 n‐=2(‐log 2 n‐+1)<4 nとなる.

ビルドアルゴリズム

リーフノードの場合
ツリー[現在のノード]=配列[現在のノード]

リーフノードでない場合

左右の子を再帰的にビルド呼び出し

ツリー[現在のノード]=ツリー[左の子]+ツリー[右の子]

時間:O(n)

Sum queries
区間和の計算は木の中で行われます.ルートノードから、必要な範囲に対して区間和を求める.
sum queryアルゴリズム
ルートから必要区間の和を求める.

(実装レベルで発生する可能性がある)l>r
は、0を返します.

現在の領域が必要な領域と完全に一致する場合
現在のノードに格納されている計算値を返します.

現在のセグメントが必要なセグメントと一致しない場合
2つのサブセクションの合計計算を要求します.

所要時間:O(log n)
最大4 log(n)個のノードにアクセスするため,O(logn)の時間的複雑さが高い.

update queries
a[i]は、ツリー内の1つのレベルのセグメントにのみ影響します.
ツリーのa[i]値は、リーフノード上に最初に存在します.ツリー内の左サブアイテムまたは右サブアイテムの1つであるため、セグメントにのみ影響します.
アルゴリズムの更新
ルートノードから、変更するインデックスに移動し、下に戻ります.閉じている場合は、戻り時に関連するセクションが更新されます.呼び出した関数がスタック内で展開された後にポップアップされる画像を想像すると、より簡単に理解できます.

所要時間:O(logn)

Implementation
ツリー構造は実際に保存されません.バイナリツリーなので配列として扱うことができます.ルートノードは1であってもよく、iの第1のサブノードの左側のサブノードは2 iであってもよく、右側のサブノードは2 i+1であってもよい.

#include <bits/stdc++.h>

#define pii pair<int,int>
#define fs first
#define sc second
#define all(v) v.begin(),v.end()
#define sorta(a) sort(all(a))

using namespace std;
typedef long long ll;

#define debug(a) for(auto x:a) cout<<x<<' '; cout<<'\n';

// given array : a
// segment Tree : t

const int MAX=1e6+100;
ll n,t[MAX*4];

void build(ll a[], int v, int tl, int tr) {
    if(tl==tr){
        t[v]=a[tl];
    }else{
        int tm=(tl+tr)/2;
        build(a,v*2,tl,tm);
        build(a,v*2+1,tm+1,tr);
        t[v]=t[v*2]+t[v*2+1];
    }
}

// v : current vertex
//tl,tr : boundaries of current vertex
//l,r : boundaries of query
ll sum(int v,int tl,int tr,int l,int r){
    if(l>r) return 0;
    if(l==tl && r==tr) return t[v]; //구하는 쿼리와 이 노드가 저장하는 범위가 꼭 일치할 때만 값 리턴
    else{   //아니면 일단 아래 자식들한테 요청
        int tm=(tl+tr)/2;
        //left child + right child
        return sum(v*2,tl,tm,l,min(tm,r)) + sum(v*2+1,tm+1,tr,max(tm+1,l),r);
    }
}

void update(int v,int tl,int tr,int pos,ll val){
    if(tl==tr){
        t[v]=val;
    }else{
        int tm=(tl+tr)/2;
        if(pos<=tm){
            update(2*v,tl,tm,pos,val);
        }else{
            update(2*v+1,tm+1,tr,pos,val);
        }
        t[v]=t[v*2]+t[v*2+1];
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int m,k; 
    cin>>n;
    cin>>m>>k;
    ll* a= new ll[n];
    for(int i=0;i<n;i++) cin>>*(a+i);
    
    build(a,1,0,n-1);

    for(int i=0;i<m+k;i++){
        ll c,l,r; cin>>c>>l>>r;
        
        if(c==1) update(1,0,n-1,l-1,r);
        else {
            l--,r--;
            cout<<sum(1,0,n-1,l,r)<<'\n';
        }
        
    }
}

Advanced versions of Segment Trees
複数のアプリケーション.

Finding the maximum and the number of times it appears

Compute the greatest common divisor/least common multiple

Counting the number of zeros, searching for the k-th zero

Finding subsegments with the maximal sum

Finding subsegments with the maximal sum
ツリー内の各ノードに4つの情報を格納します.
区間の和、最大接頭辞和、最大接尾辞和、前の3つの値の最大値
次の3つの場合、求める値はプライマリ・ツリーの論理と同じです.
1.左側の子に最大値がある
2.右側の子に最大値がある
3.左右のサブアイテムが重なる区間に最大値が存在する
したがって、求めた値は上記3つの値のうち最大値となる.
構造体を作成し、プライマリ・ツリーと同様に実装する適切なラッパ関数を作成できます.