区间修改，区间查询（线段树）

线段树

线段树－Segment Tree是一种基于分治思想的二叉树数据结构，用于区间信息修改和查询

区间修改和查询

延迟标记

延迟是设计算法和解决问题的重要思路之一，可以减少徒劳的操作，有效降低时间复杂度。
试想我们在线段树上修改区间[l,r]中的每一个元素的值，而且该区间覆盖了节点node代表的区间[node.l, node.r], 我们当然可以逐一更新子树node中的所有元素，但这个逐一更新的操作是不必要的，因为后续的询问指令可能没有用到[l,r]的子区间。即时更新完全是浪费cpu。
修改时，在节点区间被待修改目标区间完全覆盖时立即返回，回溯时向当前节点累计一个延迟标记，标记其子节点尚未更新。
所有暂时没有被修改的节点都推迟到将来必须被修改时再执行修改（后续查询或修改操作递归进入这些节点时）。
延迟标记是线段树中自上而下传递数据的方式。

例题

A Simple Problem with Integers

给定一个长度为 N 的数列 P，以及 W条指令，每条指令可能是以下两种之一：
C l r d，表示把数列中第 l~r个数都加 d。
Q l r，表示询问数列中第 l∼r个数的和。
对于每个询问，输出一个整数表示答案。
输入格式
第一行两个整数 N,W。
第二行 N个整数 P[i]。
接下来 W行表示 W条指令，每条指令的格式如题所示。
输出格式
对于每个询问，输出一个整数表示答案。
每个答案占一行。
数据范围
1≤N,W≤10⁵, |d|≤10000, |P[i]|≤10⁹
输入样例：
11 4
1 2 3 4 5 6 7 8 9 10 11
Q 5 6
Q 2 9
C 2 9 2
Q 4 10
输出样例：
11
44
61

线段树解决方案

每个节点用结构体模拟
节点包含四个分量：　区间和sum , add增量（兼作延迟标记），左右端点
broadcast函数实现了延迟标记的向下广播
本题属于区间修改，区间查询

代码实现

#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
//simple integer  
//segment tree with postpone mark

const int N = 100007;

int n, w;
int P[N];

struct STree
{
	int l,r;
	LL sum , add;
}ST[4 * N];

void pushup(int u)
{
	
	ST[u].sum = ST[u << 1].sum + ST[u << 1 | 1].sum;
	
}

void broadcast(int k)
{
	STree & root = ST[k], & left = ST[k << 1];
	STree & right = ST[k << 1 | 1];
	if(root.add)//postpone mark is valid
	{
		left.add += root.add, left.sum += (LL)(left.r - left.l + 1) * root.add;
		right.add += root.add, right.sum +=(LL)(right.r - right.l + 1) * root.add;
		root.add = 0;
	}
}
void build(int k , int l , int r)
{
	if(l == r){
		ST[k] = {l,r,P[l]};
		return;	
	} 
	
	ST[k] = {l,r};
	int mid = (l + r)>> 1;
	build(k << 1, l, mid);
	build(k << 1 | 1, mid + 1, r);
	pushup(k);
}
//change
void modify(int k , int l , int r, int d)
{
	if(ST[k].l >= l && ST[k].r <= r)
	{//whole region need to be modified
	  ST[k].sum +=(LL)(ST[k].r - ST[k].l + 1) * d;
	  ST[k].add += d;//MARK
		
	}else
	{
		broadcast(k);
		int mid = ST[k].l + ST[k].r >> 1;
		if(l <= mid) modify(k << 1, l, r, d);
		if(r > mid) modify(k << 1 | 1, l, r, d);
		pushup(k);
	}
	
}
LL ask(int k , int l , int r)
{
	if(ST[k].l >= l && ST[k].r <= r) return ST[k].sum;
	broadcast(k);//only spread one layer every time as need
	
	int mid = ST[k].l + ST[k].r >> 1;
	LL val = 0;//return answer
	if(l <= mid) val += ask(k << 1, l, r);
	if( r > mid) val += ask(k << 1|1, l, r);
	return val;
}
int main()
{
//	freopen("TEST.in","r",stdin);
//	freopen("TEST.out","w",stdout);
  scanf("%d%d",&n, &w);
  for(int i = 1; i <= n; i ++)
    scanf("%d",&P[i]);// read in
    
  build(1, 1, n);//build Segment tree
  
  int l, r, d;
  char op[2];
  while(w --)
  {
  	scanf("%s%d%d",op, &l,&r);
  	if(67 == op[0])
  	{
  		scanf("%d",&d);
  		modify(1,l,r,d);
	}else printf("%lld\n",ask(1,l,r));
  }
    
//	fclose(stdin);
//	fclose(stdout);

  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109