線段樹算法講解

問：給你一個長度為n的數組，然後詢問m次，每次詢問是給定兩個數x，y。求在【x，y】區間的數之和。

也許你會說周遊，但若n為1e6，m為1e3呢？這是可以用一種資料結構——線段樹。

線段樹的每一個點維護一個[l,r）的區間。長這樣：

線段樹算法講解

圖中，數組長度為6，第一個節點維護的是【1，6】的最大值，左節點維護的是【1,3】的最大值，以此類推，直至葉子節點。

下面，以求區間和為例來進一步說明。

定義：

const int maxn = 1e5 + 10;
struct node{
	int l, r;//左右節點 
	int data;//存儲的值 
	int mid()
	{
		return (l + r) >> 1;
	}
}sum[maxn << 2];//一般開四倍空間

線段樹的建構

void build(int root, int l, int r)
{
	sum[root].l = l, sum[root].r = r;//給每個節點所維護的區間指派 
	if(sum[root].l == sum[root].r)//到達葉子節點 
	{
		sum[root].data = a[sum[root].l];
		return;
	}
	int mid = sum[root].mid();
	build(root << 1, l, mid);//左右遞歸建樹 
	build(root << 1 | 1, mid + 1, r);
	push_up(root);//精髓所在 
}

觀察代碼，可以發現，線段樹的建構是不斷地遞歸直至葉子節點指派。葉子節點指派之後用push_up函數為其父親節點指派。

push_up函數

void push_up(int root)
{
	sum[root].data = sum[root << 1].data + sum[root << 1 | 1].data;
}

單點修改

void update(int root, int p, int v)//p位置的值加v 
{
	if(sum[root].l == sum[root].r)//找到需要修改的節點 
	{
		sum[root].data += v;
		return;
	}
	int mid = sum[root].mid();
	if(p <= mid)//若在左子節點内 
		update(root << 1, p, v);
	else if(p > mid)//若在右子節點内 
		update(root << 1 | 1, p, v);
	push_up(root);//更新父節點 
}

單點修改情況下的查詢

int query(int root, int l, int r)
{
	int ans = 0;
	if(sum[root].l >= l && sum[root].r <= r)
	{
		return sum[root].data;
	}
	int mid = sum[root].mid();
	if(mid >= l)//若所查詢區間和左子節點區間有交集 
		ans += query(root << 1, l, r);
	if(mid + 1 <= r)//若和右子節點區間有交集 
		ans += query(root << 1 | 1, l, r);
	return ans;
}

上面是單點修改的情況，下面講解區間修改

在對某個區間修改時需要用到lazy标記。當使用lzay标記某個區間時，此區間之上的區間顯示的内容是修改過的，但其子區間沒有被修改，當需要用到子區間時會通過push_down函數進行修改，這樣做主要是為了減少時間複雜度。

void update(int root, int l, int r, int v)//[l, r]區間的值更改為v 
{
	if(sum[root].l >= l && sum[root].r <= r)//目前節點區間完全在需修改區間内 
	{
		sum[root].data = v * (sum[root].r - sum[root].l + 1);
		lazy[root] = v;
		return;
	}
	push_down(root);//查詢是否有lazy标記 
	int mid = sum[root].mid();
	if(mid >= l)//與左區間有交集 
		update(root << 1, l, r, v);
	if(mid + 1 <= r)//與右區間有交集 
		update(root << 1 | 1, l, r, v);
	push_up(root);
}

push_down函數

void push_down(int root)
{
	if(lazy[root])
	{
		//lazy标記下移 
		lazy[root << 1] = lazy[root]; 
		lazy[root << 1 | 1] = lazy[root];
		//更新左右子節點區間 
		sum[root << 1].data = lazy[root] * (sum[root << 1].r - sum[root << 1].l + 1);
		sum[root << 1 | 1].data = lazy[root] * (sum[root << 1 | 1].r - sum[root << 1 | 1].l + 1);
		lazy[root] = 0;//已經下移，歸零 
	}
}

有lazy标記的查詢區間

int query(int root, int l, int r)//查詢[l, r] 區間 
{
	int ans = 0;
	if(sum[root].l >= l && sum[root].r <= r)
	{
		return sum[root].data;
	}
	push_down(root);//查詢lazy标記 
	int mid = sum[root].mid();
	if(mid >= l)
		ans += query(root << 1, l, r);
	if(mid + 1 <= r)
		ans += query(root << 1 | 1, l, r);
	return ans;
}

附上完整的單點修改和區間修改代碼：

單點修改

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;

const int maxn = 1e5 + 10;
struct node{
	int l, r;//左右節點 
	int data;//存儲的值 
	int mid()
	{
		return (l + r) >> 1;
	}
}sum[maxn << 2];//一般開四倍空間 

int a[maxn];
int n;
char str[10];

void init()
{
	mem(a, 0);
	mem(sum, 0);
}

void push_up(int root)
{
	sum[root].data = sum[root << 1].data + sum[root << 1 | 1].data;
}

void build(int root, int l, int r)
{
	sum[root].l = l, sum[root].r = r;//給每個節點所維護的區間指派 
	if(sum[root].l == sum[root].r)//到達葉子節點 
	{
		sum[root].data = a[sum[root].l];
		return;
	}
	int mid = sum[root].mid();
	build(root << 1, l, mid);//左右遞歸建樹 
	build(root << 1 | 1, mid + 1, r);
	push_up(root);//精髓所在 
}

void update(int root, int p, int v)//p位置的值加v 
{
	if(sum[root].l == sum[root].r)//找到需要修改的節點 
	{
		sum[root].data += v;
		return;
	}
	int mid = sum[root].mid();
	if(p <= mid)//若在左子節點内 
		update(root << 1, p, v);
	else if(p > mid)//若在右子節點内 
		update(root << 1 | 1, p, v);
	push_up(root);//更新父節點 
}

int query(int root, int l, int r)
{
	int ans = 0;
	if(sum[root].l >= l && sum[root].r <= r)
	{
		return sum[root].data;
	}
	int mid = sum[root].mid();
	if(mid >= l)//若所查詢區間和左子節點區間有交集 
		ans += query(root << 1, l, r);
	if(mid + 1 <= r)//若和右子節點區間有交集 
		ans += query(root << 1 | 1, l, r);
	return ans;
}

int main()
{
	int t;
	scanf("%d", &t);
	int num = 1;
	while(t--)
	{
		init();
		scanf("%d", &n);
		for(int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		build(1, 1, n);
		printf("Case %d:\n", num++);
		while(scanf("%s", str))
		{
			if(str[0] == 'E')	break;
			int x, y;
			scanf("%d%d", &x, &y);
			if(str[0] == 'A')
			{
				update(1, x, y);
			}
				
			else if(str[0] == 'S')
				update(1, x, -y);
			else if(str[0] == 'Q')
				printf("%d\n", query(1, x, y));
		}
	}
	return 0;
}

區間修改

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;

const int maxn = 5e5;
struct node{
	int l, r;
	int data;
	int mid()
	{
		return (l + r) >> 1;
	}
}sum[maxn << 2];

int lazy[maxn];
int n;

void init()
{
	mem(sum, 0);
	mem(lazy, 0);
}

void push_up(int root)
{
	sum[root].data = sum[root << 1].data + sum[root << 1 | 1].data;
}

void build(int root, int l, int r)
{
	sum[root].l = l, sum[root].r = r;
	if(sum[root].l == sum[root].r)
	{
		
//		sum[root].data = a[sum[root].l];
		sum[root].data = 1;
		return;
	}
	int mid = sum[root].mid();
	build(root << 1, l, mid);
	build(root << 1 | 1, mid + 1, r);
	push_up(root);
}

void push_down(int root)
{
	if(lazy[root])
	{
		//lazy标記下移 
		lazy[root << 1] = lazy[root]; 
		lazy[root << 1 | 1] = lazy[root];
		//更新左右子節點區間 
		sum[root << 1].data = lazy[root] * (sum[root << 1].r - sum[root << 1].l + 1);
		sum[root << 1 | 1].data = lazy[root] * (sum[root << 1 | 1].r - sum[root << 1 | 1].l + 1);
		lazy[root] = 0;//已經下移，歸零 
	}
}

void update(int root, int l, int r, int v)//[l, r]區間的值更改為v 
{
	if(sum[root].l >= l && sum[root].r <= r)//目前節點區間完全在需修改區間内 
	{
		sum[root].data = v * (sum[root].r - sum[root].l + 1);
		lazy[root] = v;
		return;
	}
	push_down(root);//查詢是否有lazy标記 
	int mid = sum[root].mid();
	if(mid >= l)//與左區間有交集 
		update(root << 1, l, r, v);
	if(mid + 1 <= r)//與右區間有交集 
		update(root << 1 | 1, l, r, v);
	push_up(root);
}

int query(int root, int l, int r)//查詢[l, r] 區間 
{
	int ans = 0;
	if(sum[root].l >= l && sum[root].r <= r)
	{
		return sum[root].data;
	}
	push_down(root);//查詢lazy标記 
	int mid = sum[root].mid();
	if(mid >= l)
		ans += query(root << 1, l, r);
	if(mid + 1 <= r)
		ans += query(root << 1 | 1, l, r);
	return ans;
}

int main()
{
	int t;
	scanf("%d", &t);
	int num = 1;
	while(t--)
	{
		init();
		scanf("%d", &n);
		int m;
		build(1, 1, n);
		scanf("%d", &m);
		for(int i = 0; i < m; i++)
		{
			int x, y, z;
			scanf("%d%d%d", &x, &y, &z);
			update(1, x, y, z);
		}
		printf("Case %d: The total value of the hook is %d.\n", num++, sum[1].data);
	}
	return 0;
}

OK，上課去了，，應該還來得及。。逃

線段樹算法講解

線段樹算法講解

線段樹的建構

push_up函數

單點修改

單點修改情況下的查詢

繼續閱讀

ACdream 1162 胖子教你線段樹

HDU 5669 Road

UVALive 7141 BombX

HDU 5023 A Corrupt Mayor's Performance Art （線段樹）

hdu 5023 A Corrupt Mayor's Performance Art

[HDU5023]A Corrupt Mayor's Performance Art

hdu 5023 A Corrupt Mayor's Performance Art（線段樹+位運算）

【HDU 5023】A Corrupt Mayor's Performance Art 【線段樹+狀态壓縮】

HDU5023(A Corrupt Mayor‘s Performance Art)

A Corrupt Mayor's Performance Art HDU - 5023

hdu 5023 A Corrupt Mayor's Performance Art(線段樹區間更新)

洛谷 P3373 【模闆】線段樹 2

WIKIOI 1282 約瑟夫問題

遲來的4月小結

HDU 3397 Sequence operation

HDU 5381 The sum of gcd