線段樹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: Current tree's root 代表當前建樹的根節點
  l: Current node's left interval 當前節點區間左側
  r: Current node's right interval 當前節點區間右側
  */
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;
}

Done！#

Tip

可以在luogu 模板題 1中嘗試你學到的知識。
以上代碼不保證 AC。