線分木segmentTree、ここにあなたが知っておくべきすべてのポイントがあります

カバー画像は本文とは関係ありません。筆者がこのブログを書いているときにちょうど聞いていました〜

一、線分木の存在意義#

線分木は区間情報を管理するデータ構造で、単点修正、区間修正、区間クエリ を主とする一連の操作の時間計算量を $O(logn)$ に制御できます。

二、線分木の原理#

線分木は二分探索木の一種です。これは分治法の考え方を利用しており、区間加算に関する問題に対しては、より小さなサブ問題に分割し続けることで、サブ問題を直接解決できるまで進めます。

[!NOTE]
区間加算とは何ですか？
区間 [L,R] に対する問題の答えが、区間 [L,M] と [M+1,R] の答えを統合することで得られる場合に、その問題は区間加算を満たします。

線分木の設計思想は以下のフローチャートで表すことができます。長さが $[1,10]$ の区間に対して、分治法を用いて、最大で図に示すように最小長さ 1 のサブ問題に分割できます。
線分木素材

実際の問題を解決するために、区間内の要素の合計を表すvalue変数を導入します（要素はすべて整数型で、合計の範囲はlong long内と仮定します）。

木構造のコード実装#

#define range 100000;
long long values[range];//区間を模擬
struct node{
  int l, r;
  int value;
  int lazy;//遅延フラグ、区間修正を制御するために使用、後で説明します
}node[4 * range];//木の最大長さは4 * range
void push_up(int i){
  node[i].value = node[i << 1].value + node[i << 1 | 1].value;
}
/**
  * @param 
  i: 現在の木の根を表す
  l: 現在のノードの左区間
  r: 現在のノードの右区間
  */
void build(int i, int l, int r){
  node[i] = { l, r, 0, 0 };
  //すでに最小区間
  if（l == r){
    node[i].value = values[l];
    return ;
  }
  int mid = (l + r) >> 1;
  build(i << 1, l, mid);
  build(i << 1 | 1, mid + 1, r);
  push_up(i);
  return node[i].value;
}

三、線分木の操作#

前述のように、線分木は区間操作を実現するために設計されており、増減修正は ** 修正 (modify) とクエリ (query)** 操作のみを実行できます。

区間クエリ#

クエリ操作は非常に簡単です。クエリ区間 $[l, r]$ が与えられた場合、根ノードから下に向かって検索し、ノードの区間がクエリ区間内にある場合はその value を加算します。そうでない場合、交差があれば、子ノードを引き続きクエリします。

long long query(int i,int l,int r){
  int rangeL = node[i].l;
  int rangeR = node[i].r;
  int mid = (rangeL + rangeR) >> 1;
  int ans = 0;
  if(l <= rangeL && r >= rangeR){
    return node[i].value;
  }
  //左側の子区間と交差
  if(l <= mid){
     ans += query(i << 1, l, r);
  }
  //右側の子区間と交差
  if(r > mid){
     ans += query(i << 1 | 1, l, r);
  }
  return ans;
}

修正#

まず単点修正について説明します。単点修正は根要素の DFS から始め、ターゲットポイントを見つけるだけです。注意すべきは、経路上のすべてのノードを同期して修正する必要があることです。

void point_modify(int i, int target, int k){
  int rangeL = node[i].l;
  int rangeR = node[i].r;
  if(rangeL == rangeR){//ターゲットポイントを見つけた
    node[target].value += k;//操作は任意
  }
  int mid = (rangeL + rangeR) >> 1;
  if(target <= mid){
    modify(i << 1, target, k);
  }
  else{
    modify(i << 1 | 1, target, k);
  }
  //経路を修正
  push_up(i);
}

区間修正はこの操作をそのまま使用することはできません。そうしないと、修正の時間計算量が $O(nlogn)$ になり、受け入れられません。
そのため、検索中に最小ノードまでではなく、大きな区間までしか検索しない方法を設計し、修正値を保存するための変数 lazytag を付加します。区間のサブセットを操作する必要がある場合は、lazytag を下に伝播してサブ区間の値を修正します。コード実装：

void push_down(int i, int l, int r){
  if(node[i].lazy){
    int mid=(l+r)>>1;
    node[i<<1].lazy = node[i].lazy;
    node[i<<1|1].lazy = node[i].lazy;
    //遅延フラグを下に伝播
    node[i<<1].value += node[i].lazy * (mid - l + 1);
    node[i<<1|1].value += node[i].lazy * (r - mid);
    //値を更新
    node[i].lazy = 0;
  }
}

void range_modify(int i, int l, int r, int k){
  int rangeL = node[i].l;
  int rangeR = node[i].r;
  if(l >= rangeL && r <= rangeR){
    node[i].lazy = k;
    node[i].value += k * (r - l + 1);
    return ;
  }
  //子ノードの修正を下に伝播
  push_down(i, rangeL, rangeR);
  int mid = (rangeL + rangeR) >> 1;
  if(l <= mid){
    range_modify(i << 1, l, r, k);
  }
  if(r > mid){
    range_modify(i << 1 | 1, l, r, k);
  }
  //経路を修正
  push_up(i);
}

long long range_query(int i,int l,int r){
  int rangeL = node[i].l;
  int rangeR = node[i].r;
  //子ノードをクエリするために、lazytagを下に伝播
  push_down(i, rangeL, rangeR);
  int mid = (rangeL + rangeR) >> 1;
  int ans = 0;
  if(l <= rangeL && r >= rangeR){
    return node[i].value;
  }
  //左側の子区間と交差
  if(l <= mid){
     ans += range_query(i << 1, l, r);
  }
  //右側の子区間と交差
  if(r > mid){
     ans += range_query(i << 1 | 1, l, r);
  }
  return ans;
}

完了！#

[!TIP]
学んだ知識を使ってluogu テンプレート問題 1で試してみてください。
上記のコードは AC を保証するものではありません。