本質為 加了左右端點的樹形結構

線段樹

資料型別構造

struct node{
	int l,r;  //l左端點    r右端點
	int val;  //val值域
}n[maxn];     //n[i]表示標號為i的樹的結點

基本操作

構造線段樹

void make(int left,int right, int num);

引數說明：

??left—right：即左端點—右端點，最大區間；

??num：標號，一般為1，

添加結點

void add(int i,int j,int num);

引數說明：

??i：欲加到的目的點；

??j：欲加點的個數；

??num：標號，一般為1，

洗掉結點

void sub(int i,int j,int num);

引數說明：

??i：欲加到的目的點；

??j：欲加點的個數；

??num：標號，一般為1，

查詢結點

void query(int l, int r,int num);

引數說明：

??l-r：詢問區間，該函式會利用sum存盤的權值和來查詢l-r的個數；

??num：標號，一般為1.

實作原理

構造線段樹

利用性質：

??1> 標號為i的結點，其左孩子標號2i，右孩子標號2i+1，父親標號i/2；

??2> 線段樹中，兩端點為a、b的一個點，其左孩子兩端點為a、mid，右孩子兩端點mid+1，b；

??3> 左右端點相等時，訪問到葉子結點

思路：

對于每個結點

val計算方法為：val = 左.val + 右.val

添加結點

??自頂向下的樹的操作，自根加到結點的操作，

思路：

??從根向下訪問，若i在左孩子區間內，則+j,否則訪問右孩子，（i不在左孩子中，則必在右孩子中）

從根開始，到葉子結點停止

洗掉結點

添加結點的反操作，將 ’+‘ 改為 ’-‘ 即可，

查詢結點

設當前點的兩端為a、b，目標點的兩端為l、r

利用分類思想

l、r在哪個區段內，就訪問哪個區段

思路：

C++代碼實作

構建線段樹

void make(int x, int y, int num){//構造
	t[num].l=x,t[num].r=y;
	if(x==y)
		t[num].val=val;  //到葉子結點賦值，結束
	else{
		make(x, ( x + y ) / 2, 2 * num);//遞回構造左子樹
		make(( x + y ) / 2 + 1, y, 2 * num + 1);//遞回構造右子樹
		t[num].val = t[2*num].val + t[2*num+1].val;//計算val
	}	
}

添加結點

void add(int i, int j, int num){//增加
	t[num].val += j;//val+j
	if(t[num].l==i && t[num].r==i)//找到結點
		return;
	if(i>(t[num].l + t[num].r) / 2)//i在右孩子中
		add(i, j, 2 * num + 1);
	else						//i在左孩子中
		add(i, j, 2 * num);
}

洗掉結點

void add(int i, int j, int num){//增加
	t[num].val -= j;//val+j
	if(t[num].l==i && t[num].r==i)//找到結點
		return;
	if(i>(t[num].l + t[num].r) / 2)//i在右孩子中
		add(i, j, 2 * num + 1);
	else						//i在左孩子中
		add(i, j, 2 * num);
}

查詢結點

void query(int l, int r, int num){//查詢
	if(l<=t[num].l && r>=t[num].r)//在目標區間內，記錄權值和SUM
		SUM += t[num].val;
	else{			//不在目標區間內，進行分類
		int mid = (t[num].l + t[num].r)/2;
		if(l>mid)//在右孩子中
			query(l, r, 2 * num + 1);
		else if(r<=mid)//在左孩子中
			query(l, r, 2 * num);
		else{//左右孩子中均有
			query(l, r, 2 * num);
			query(l, r, 2 * num + 1);
		}
	}
}

Lazy tags優化

區間更新：修改一段連續區間的值

Lazy tags優化：

??如名所示，懶標記優化法（眾所周知，懶人創造效率）

??關鍵思路：修改時只修改對查詢有用的點，對于未更新完全的點打上懶標記，待需要時再進行更新

實體應用

1. P3372 【模板】線段樹 1
   題目描述：
   ?????如題，已知一個數列，你需要進行下面兩種操作：
   ????1. 將某區間每一個數加上 k，
   ????2. 求出某區間每一個數的和，
   代碼如下:

#include<iostream>
#include<cstdio>
#define MAXN 1000001
#define ll long long
using namespace std;
unsigned ll n,m,a[MAXN],ans[MAXN<<2],tag[MAXN<<2];
inline ll ls(ll x)
{
    return x<<1;
}
inline ll rs(ll x)
{
    return x<<1|1;
}
void scan()
{
    cin>>n>>m;
    for(ll i=1;i<=n;i++)
    scanf("%lld",&a[i]);
}
inline void push_up(ll p)
{
    ans[p]=ans[ls(p)]+ans[rs(p)];
}
void build(ll p,ll l,ll r)
{
    tag[p]=0;
    if(l==r){ans[p]=a[l];return ;}
    ll mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
} 
inline void f(ll p,ll l,ll r,ll k)
{
    tag[p]=tag[p]+k;
    ans[p]=ans[p]+k*(r-l+1);
}
inline void push_down(ll p,ll l,ll r)
{
    ll mid=(l+r)>>1;
    f(ls(p),l,mid,tag[p]);
    f(rs(p),mid+1,r,tag[p]);
    tag[p]=0;
}
inline void update(ll nl,ll nr,ll l,ll r,ll p,ll k)
{
    if(nl<=l&&r<=nr)
    {
        ans[p]+=k*(r-l+1);
        tag[p]+=k;
        return ;
    }
    push_down(p,l,r);
    ll mid=(l+r)>>1;
    if(nl<=mid)update(nl,nr,l,mid,ls(p),k);
    if(nr>mid) update(nl,nr,mid+1,r,rs(p),k);
    push_up(p);
}
ll query(ll q_x,ll q_y,ll l,ll r,ll p)
{
    ll res=0;
    if(q_x<=l&&r<=q_y)return ans[p];
    ll mid=(l+r)>>1;
    push_down(p,l,r);
    if(q_x<=mid)res+=query(q_x,q_y,l,mid,ls(p));
    if(q_y>mid) res+=query(q_x,q_y,mid+1,r,rs(p));
    return res;
}
int main()
{
    ll a1,b,c,d,e,f;
    scan();
    build(1,1,n);
    while(m--)
    {
        scanf("%lld",&a1);
        switch(a1)
        {
            case 1:{
                scanf("%lld%lld%lld",&b,&c,&d);
                update(b,c,1,n,1,d);
                break;
            }
            case 2:{
                scanf("%lld%lld",&e,&f);
                printf("%lld\n",query(e,f,1,n,1));
                break;
            }
        }
    }
    return 0;
}

2. P3373 【模板】線段樹 2
   題目描述：
   ???? 如題，已知一個數列，你需要進行下面三種操作：
   ????1. 將某區間每一個數乘上 x
   ????2. 將某區間每一個數加上 x
   ????3. 求出某區間每一個數的和
   代碼如下：

#include <iostream>
#include <cstdio>
using namespace std;
//題目中給的p
int p;
//暫存數列的陣列
long long a[100007];
//線段樹結構體，v表示此時的答案，mul表示乘法意義上的lazytag，add是加法意義上的
struct node{
    long long v, mul, add;
}st[400007];
//buildtree
void bt(int root, int l, int r){
//初始化lazytag
    st[root].mul=1;
    st[root].add=0;
    if(l==r){
        st[root].v=a[l];
    }
    else{
        int m=(l+r)/2;
        bt(root*2, l, m);
        bt(root*2+1, m+1, r);
        st[root].v=st[root*2].v+st[root*2+1].v;
    }
    st[root].v%=p;
    return ;
}
//核心代碼，維護lazytag
void pushdown(int root, int l, int r){
    int m=(l+r)/2;
//根據我們規定的優先度，兒子的值=此刻兒子的值*爸爸的乘法lazytag+兒子的區間長度*爸爸的加法lazytag
    st[root*2].v=(st[root*2].v*st[root].mul+st[root].add*(m-l+1))%p;
    st[root*2+1].v=(st[root*2+1].v*st[root].mul+st[root].add*(r-m))%p;
//很好維護的lazytag
    st[root*2].mul=(st[root*2].mul*st[root].mul)%p;
    st[root*2+1].mul=(st[root*2+1].mul*st[root].mul)%p;
    st[root*2].add=(st[root*2].add*st[root].mul+st[root].add)%p;
    st[root*2+1].add=(st[root*2+1].add*st[root].mul+st[root].add)%p;
//把父節點的值初始化
    st[root].mul=1;
    st[root].add=0;
    return ;
}
//update1，乘法，stdl此刻區間的左邊，stdr此刻區間的右邊，l給出的左邊，r給出的右邊
void ud1(int root, int stdl, int stdr, int l, int r, long long k){
//假如本區間和給出的區間沒有交集
    if(r<stdl || stdr<l){
        return ;
    }
//假如給出的區間包含本區間
    if(l<=stdl && stdr<=r){
        st[root].v=(st[root].v*k)%p;
        st[root].mul=(st[root].mul*k)%p;
        st[root].add=(st[root].add*k)%p;
        return ;
    }
//假如給出的區間和本區間有交集，但是也有不交叉的部分
//先傳遞lazytag
    pushdown(root, stdl, stdr);
    int m=(stdl+stdr)/2;
    ud1(root*2, stdl, m, l, r, k);
    ud1(root*2+1, m+1, stdr, l, r, k);
    st[root].v=(st[root*2].v+st[root*2+1].v)%p;
    return ;
}
//update2，加法，和乘法同理
void ud2(int root, int stdl, int stdr, int l, int r, long long k){
    if(r<stdl || stdr<l){
        return ;
    }
    if(l<=stdl && stdr<=r){
        st[root].add=(st[root].add+k)%p;
        st[root].v=(st[root].v+k*(stdr-stdl+1))%p;
        return ;
    }
    pushdown(root, stdl, stdr);
    int m=(stdl+stdr)/2;
    ud2(root*2, stdl, m, l, r, k);
    ud2(root*2+1, m+1, stdr, l, r, k);
    st[root].v=(st[root*2].v+st[root*2+1].v)%p;
    return ;
}
//訪問，和update一樣
long long query(int root, int stdl, int stdr, int l, int r){
    if(r<stdl || stdr<l){
        return 0;
    }
    if(l<=stdl && stdr<=r){
        return st[root].v;
    }
    pushdown(root, stdl, stdr);
    int m=(stdl+stdr)/2;
    return (query(root*2, stdl, m, l, r)+query(root*2+1, m+1, stdr, l, r))%p;
}
int main(){
    int n, m;
    scanf("%d%d%d", &n, &m, &p);
    for(int i=1; i<=n; i++){
        scanf("%lld", &a[i]);
    }
    bt(1, 1, n);
    while(m--){
        int chk;
        scanf("%d", &chk);
        int x, y;
        long long k;
        if(chk==1){
            scanf("%d%d%lld", &x, &y, &k);
            ud1(1, 1, n, x, y, k);
        }
        else if(chk==2){
            scanf("%d%d%lld", &x, &y, &k);
            ud2(1, 1, n, x, y, k);
        }
        else{
            scanf("%d%d", &x, &y);
            printf("%lld\n", query(1, 1, n, x, y));
        }
    }
    return 0;
}