今天介紹有關線段樹的相關部分的知識，線段樹是樹的數據結構中十分重要的算法處理思想。

1.建立初始樹的條件

2.基本框架

3.區間修改的相關代碼

4.區間查詢的代碼

題目描述

給定一個長度為?N?的數組?a，其初值分別為?a1?,a2?,...,aN?。

現有?Q?個操作，操作有以下兩種：

• 1 l r k，將區間?al?,al+1?,...ar??的值加上?k。
• 2 l r，求區間?al,al+1,...,aral 的和為多少。

輸入描述

輸入第?1行包含兩個正整數?N,Q，分別表示數組?a?的長度和操作的個數。

第?2?行包含?N?個非負整數?a1?,a2?,...,aN?，表示數組?a?元素的初值。

第?3～Q?2?行每行表示一共操作，格式為以下兩種之一：

• 1 l r x
• 2 l r

其含義如題所述。

1≤N,Q≤105，1≤l≤r≤N，?109≤k,ai?≤109。

輸出描述

輸出共?Q行，每行包含一個整數，表示相應查詢的答案。

輸入輸出樣例

5 5
1 2 3 4 5
2 1 2
1 2 3 1
2 1 3
1 1 5 1
2 1 5

3
8
22

代碼部分：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 1e5+5; 
int n;
int a[N];
ll t[4*N],lz[4*N];void pushup(int o){t[o]=t[o<<1]+t[o<<1|1];
}
void pushdown(int s,int e,int o){if(lz[o]){int ls=o<<1,rs=o<<1|1;int mid=s+e>>1;t[ls]+=(mid-s+1)*lz[o],lz[ls]+=lz[o];t[rs]+=(e-mid)*lz[o],lz[rs]+=lz[o];lz[o]=0; }
}
void build(int s=1,int e=n,int o=1){if(s==e){t[o]=a[s];return;}int mid=s+e>>1;build(s,mid,o<<1);build(mid+1,e,o<<1|1);pushup(o);
}
void update(int l,int r,ll v,int s=1,int e=n,int o=1){if(s>=l&&e<=r){lz[o]+=v;t[o]+=(e-s+1)*v;return;}int mid=s+e>>1;pushdown(s,e,o);if(mid>=l) update(l,r,v,s,mid,o<<1);if(mid+1<=r) update(l,r,v,mid+1,e,o<<1|1);pushup(o);
}
ll query(int l,int r,int s=1,int e=n,int o=1){if(s>=l&&e<=r){return t[o];}int mid=s+e>>1;pushdown(s,e,o);ll res=0;if(mid>=l) res+=query(l,r,s,mid,o<<1);if(mid+1<=r) res+=query(l,r,mid+1,e,o<<1|1);return res;
}void solve() {int op;cin>>op;if(op==1){int l,r,v;cin>>l>>r>>v;update(l,r,v);}else{int l,r;cin>>l>>r;cout<<query(l,r)<<endl;}
}
int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;int q;cin>>q;for(int i=1;i<=n;i++) cin>>a[i];build();    while(q--) {solve();}return 0;
}

問題描述

給定一個長度為?N?的數列?A1?,A2?,?,AN??。現在小藍想通過若干次操作將 這個數列中每個數字清零。

每次操作小藍可以選擇以下兩種之一:

1. 選擇一個大于 0 的整數, 將它減去 1 ;
2. 選擇連續?K?個大于 0 的整數, 將它們各減去 1 。

小藍最少經過幾次操作可以將整個數列清零?

輸入格式

輸入第一行包含兩個整數?N?和?K?。

第二行包含?N?個整數?A1?,A2?,?,AN??。

輸出格式

輸出一個整數表示答案。

輸入案例：

4 2
1 2 3 4

輸出案例：

6

代碼部分：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
ll lz[N * 4], t[N * 4], a[N], n, k, ans;void pushup(ll o)
{t[o] = min(t[o << 1], t[o << 1 | 1]);
}void build(ll s = 1, ll e = n, ll o = 1)
{if (s == e){t[o] = a[s];return;}ll mid = s + e >> 1;build(s, mid, o << 1);build(mid + 1, e, o << 1 | 1);pushup(o);
}void pushdown(ll s, ll e, ll o)
{if (lz[o]){ll ls = o << 1, rs = o << 1 | 1, mid = s + e >> 1;t[ls] -= lz[o], lz[ls] += lz[o];t[rs] -= lz[o], lz[rs] += lz[o];lz[o] = 0;}
}void update(ll l, ll r, ll v, ll s = 1, ll e = n, ll o = 1)
{if (l <= s && e <= r){t[o] -= v;lz[o] += v;return;}ll mid = s + e >> 1;pushdown(s, e, o);if (mid >= l)update(l, r, v, s, mid, o << 1);if (mid + 1 <= r)update(l, r, v, mid + 1, e, o << 1 | 1);pushup(o);
}ll query(ll l, ll r, ll s = 1, ll e = n, ll o = 1)
{if (l <= s && e <= r)return t[o];ll mid = s + e >> 1;pushdown(s, e, o);ll res = 1e9;if (mid >= l)res = min(res, query(l, r, s, mid, o << 1));if (mid + 1 <= r)res = min(res, query(l, r, mid + 1, e, o << 1 | 1));return res;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> k;for (ll i = 1; i <= n; ++i)cin >> a[i];build();for (ll i = 1; i <= n; ++i){if (i + k - 1 <= n) // 還可以執行k操作{// 詢問得到最小值ll x = query(i, i + k - 1);if (x != 0){ans += x;update(i, i + k - 1, x);}}ll y = query(i, i);if (y != 0){ans += y;update(i, i, y);}}cout << ans;
}

update(i, i + k - 1, x)，可以直接減去x，這樣就可以提高效率。

今天的分享就到這里，關于線段樹的內容是算法比賽中經常考察的部分，希望大家能有所收獲。