線段樹（線段樹入門筆記）

什麼是線段樹

線段樹是一種二叉搜尋樹，它将一個區間劃分成一些單元區間，每個單元區間對應線段樹中的一個葉結點。

對于線段樹中的每一個非葉節點[a,b]，它的左兒子表示的區間為[a,(a+b)/2]，右兒子表示的區間為[(a+b)/2+1,b]。是以線段樹是平衡二叉樹，最後的子節點數目為N，即整個線段區間的長度。

定義結點

一般定義成結構體類型，其成員可以根據需要增加

struct node{
  int l;//左區間端點 
  int r;//右區間端點 
  int val;//此節點存值 
  int len;//子結點管理區間長度 
}tree[1005];      

建樹

void build(int cur, int l, int r)
{
  int mid=(l+r)/2;
  tree[cur].l=l, tree[cur].r=r;
  tree[cur].val=0, tree[cur].len=r-l+1;
  if (l==r)//隻有到達葉結點時才把數組的值賦給它 
    tree[cur].val=arr[l];//arr為輸入資料的數組
  else{
    build(cur*2, l, mid);
    build(cur*2+1, mid+1, r);
    tree[cur].val=tree[cur*2].val+tree[cur*2+1].val;//回溯過程中更新父結點 
  }
}      

單點更新

void updata(int cur, int id, int val)//cur為節點編号，id為修改資料的編号，val為增加的值 
{
  int l=tree[cur].l, r=tree[cur].r;
  int mid=(l+r)/2;
  if (l==r){
    tree[cur].val+=val;
    return;
  }
  if (id<=mid)
    updata(cur*2, id, val);
  else
    updata(cur*2+1, id, val);
  tree[cur].val=tree[cur*2].val+tree[cur*2+1].val;//回溯過程中更新父結點 
}      

區間查詢

int query(int cur, int ql, int qr)
{
  int l=tree[cur].l, r=tree[cur].r;
  int mid=(l+r)/2, res=0;
  if (ql<=l && r<=qr)//如果此節點的區間在查詢區間内，直接傳回 
    return tree[cur].val;
  if (ql<=mid)
    res+=query(cur*2, ql, qr);
  if (qr>mid)//注意這裡是兩個if，不是分支關系 
    res+=query(cur*2+1, ql, qr);
  return res;
}      

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

struct node{
  int l;
  int r;
  int val;
  int len;
  int lazy;
}tree [505];
int arr[505];

void pushup(int cur){
  tree[cur].val=tree[cur*2].val+tree[cur*2+1].val;
}

void pushdown(int cur){
  if (tree[cur].lazy!=0){
    tree[cur*2].lazy+=tree[cur].lazy;
    tree[cur*2+1].lazy+=tree[cur].lazy;
    tree[cur*2].val+=tree[cur*2].len*tree[cur].lazy;
    tree[cur*2+1].val+=tree[cur*2+1].len*tree[cur].lazy;
    tree[cur].lazy=0;
  }
}
//建樹 
void build(int cur, int l, int r){
  int mid=(l+r)/2;
  tree[cur].l=l, tree[cur].r=r;
  tree[cur].val=0, tree[cur].len=r-l+1;
  tree[cur].lazy=0;
  if (l==r)
    tree[cur].val=arr[l];
  else{
    build(cur*2, l, mid);
    build(cur*2+1, mid+1, r);
    pushup(cur);
  }
}

//單點更新  加值 
void update_point(int cur, int pos, int val)//cur為節點編号，id為修改資料的編号，val為增加的值 
{
  int l=tree[cur].l, r=tree[cur].r;
  int mid=(l+r)/2;
  if (l==r){
    tree[cur].val+=val;
    tree[cur].lazy+=val;
    return;
  }
  if (pos<=mid)
    update_point(cur*2, pos, val);
  else
    update_point(cur*2+1, pos, val);
  pushup(cur);
} 
//單點查詢
int query_point(int cur, int pos){
  if (tree[cur].l==tree[cur].r)
    return tree[cur].val;
  pushdown(cur);
  
  int mid=(tree[cur].l+tree[cur].r)/2;
  if (pos<mid)
    query_point(cur*2, pos);
  else
    query_point(cur*2+1, pos);
} 
//區間查詢
int query_interval(int cur, int ql, int qr){
  if (ql<=tree[cur].l && tree[cur].r<=qr)
    return tree[cur].val;
  pushdown(cur);
  
  int ans=0;
  int mid=(tree[cur].l+tree[cur].r)/2;
  if (ql<=mid)
    ans+=query_interval(cur*2, ql, qr);
  if (qr>mid)
    ans+=query_interval(cur*2+1, ql, qr);
  return ans; 
} 
//區間更新 加值 
void update_interval(int cur, int l, int r, int val){
  if (l<=tree[cur].l && tree[cur].r<=r){
    tree[cur].val+=(tree[cur].r-tree[cur].l+1)*val;
    tree[cur].lazy+=val;
    return;
  }
  pushdown(cur);
  
  int mid=(tree[cur].l+tree[cur].r)/2;
  if (l<=mid)
    update_interval(cur*2, l, r, val);
  if (r>mid)
    update_interval(cur*2+1, l, r, val);
  
  pushup(cur);
} 
int main(){
  
  return 0;
}