洛谷 P3372 【模闆】線段樹 1

傳送門

思路

前幾天學了線段樹的我，今天又去做了一遍線段樹【模闆】\(1\)，發現自己打代碼真的是漏洞百出啊，不過最後還是對了，是以來水一篇部落格

首先，這道模闆題的要求就是：

1.區間加

2.區間求和

這兩個操作都屬于線段樹的基本操作

前置——宏定義

#define N 100011
#define lson rt << 1
#define rson rt << 1 | 1
#define int long long
           

由于我特别懶，不想寫什麼\(rt << 1\)之類的東西，是以直接宏定義就好了，還有，為了不改\(int\)，我直接把\(int\)宏定義為\(long \ long\)，省的麻煩（我真的是懶到家了）

1.定義

int sum[N << 2], lazy[N << 2], n, m;
           

衆所周知，線段樹一般要開四倍空間，不明白的可以自己畫一顆線段樹數一下，sum數組維護區間和，lazy是懶标記

2.pushup

inline void pushup(int rt) {
	sum[rt] = sum[lson] + sum[rson];
}
           

這是一個上傳給父親結點的資訊的函數，目前節點的區間和就等于它左兒子和右兒子的區間和之和

2.建樹

void build(int l, int r, int rt) {
	if(l == r) {
		sum[rt] = read();
		return;
	}
	int m = (l + r) >> 1;
	build(l, m, lson);
	build(m + 1, r, rson);
	pushup(rt);
}
           

上面是建樹過程,\(rt\)表示目前節點，\(lson\)是左孩子，\(rson\) 是右孩子

3.标記下放

inline void pushdown(int l, int r, int rt) {
	if(!lazy[rt]) return;
	lazy[lson] += lazy[rt];
	lazy[rson] += lazy[rt];
	int m = (l + r) >> 1;
	sum[lson] += (m - l + 1) * lazy[rt];
	sum[rson] += (r - m) * lazy[rt];
	lazy[rt] = 0;
	return;
}
           

pushdown函數的實作：

1.用lazy存儲這個懶标記。

2.遞歸到這個節點時，隻更新這個節點的狀态，并把目前的更改值累積到标記中。

什麼時候才用到這個懶标記？

當需要遞歸這個節點的子節點時，标記下傳給子節點。

3.下放操作：（三步）

目前節點的懶标記累積到子節點的懶标記中。

修改子節點狀态。

父節點懶标記清0。

4.區間修改

void update(int L, int R, int c, int l, int r, int rt) {
	if(L <= l && r <= R) {
		sum[rt] += c * (r - l + 1);
		lazy[rt] += c;
		return;
	}
	pushdown(l, r, rt);
	int m = (l + r) >> 1;
	if(L <= m) update(L, R, c, l, m, lson);
	if(R > m) update(L, R, c, m + 1, r, rson);
	pushup(rt);
}

           

5.區間求和

int query(int L, int R, int l, int r, int rt) {
	if(L <= l && r <= R) return sum[rt];
	pushdown(l, r, rt);
	int m = (l + r) >> 1, ans = 0;
	if(L <= m) ans += query(L, R, l, m, lson);
	if(R > m) ans += query(L, R, m + 1, r, rson);
	return ans;
}
           

代碼

下面上傳高清無碼無水印代碼

#include <bits/stdc++.h>
#define N 100011
#define lson rt << 1
#define rson rt << 1 | 1
#define int long long
using namespace std;

int sum[N << 2], lazy[N << 2], n, m;

inline int read() {
	char c = getchar();
	int x = 0, f = 1;
	for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
	return x * f;
}

inline void pushup(int rt) {
	sum[rt] = sum[lson] + sum[rson];
}

void build(int l, int r, int rt) {
	if(l == r) {
		sum[rt] = read();
		return;
	}
	int m = (l + r) >> 1;
	build(l, m, lson);
	build(m + 1, r, rson);
	pushup(rt);
}

inline void pushdown(int l, int r, int rt) {
	if(!lazy[rt]) return;
	lazy[lson] += lazy[rt];
	lazy[rson] += lazy[rt];
	int m = (l + r) >> 1;
	sum[lson] += (m - l + 1) * lazy[rt];
	sum[rson] += (r - m) * lazy[rt];
	lazy[rt] = 0;
	return;
}

void update(int L, int R, int c, int l, int r, int rt) {
	if(L <= l && r <= R) {
		sum[rt] += c * (r - l + 1);
		lazy[rt] += c;
		return;
	}
	pushdown(l, r, rt);
	int m = (l + r) >> 1;
	if(L <= m) update(L, R, c, l, m, lson);
	if(R > m) update(L, R, c, m + 1, r, rson);
	pushup(rt);
}

int query(int L, int R, int l, int r, int rt) {
	if(L <= l && r <= R) return sum[rt];
	pushdown(l, r, rt);
	int m = (l + r) >> 1, ans = 0;
	if(L <= m) ans += query(L, R, l, m, lson);
	if(R > m) ans += query(L, R, m + 1, r, rson);
	return ans;
}

signed main() {
	n = read(), m = read();
	build(1, n, 1);
	for(int i = 1; i <= m; i++) {
		int opt = read(), x = read(), y = read();
		if(opt == 1) {
			int k = read();
			update(x, y, k, 1, n, 1);
		}
		if(opt == 2) cout << query(x, y, 1, n, 1) << '\n';
	}
	return 0;
}
           

轉載不必聯系作者，但請聲明出處