这篇文章上次修改于 238 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

ACM程序课算法笔记13——线段树入门

线段树介绍

线段树的功能是维护一个数组，当然你可以用普通数组维护，线段树只是一种维护方式，它的特点是可以在O(LogN)的时间复杂度完成单点修改，区间修改，区间查询。

线段树结构

线段树的结构目的是为了维护区间的某个信息，比如总和，最大值，最小值等等。

按照树的思想，把区间进行多次的分割，同时，线段树使用数组存储树，使用数组表示树可以使根节点编号为1。

例如区间[1,5] 我们根据树先进行分割一次[1, 3]和[4, 5]这就是一个根节点变成两个子节点。同时在对它们俩进行一个拆分，此时[1,3]变成[1,2]和[3,3]。[4, 5]拆成[4,4]和[5,5]结构如下图

还有一点需要注意的是，线段树不一定要维护总和，我们可以用一个节点来做一些例子：(此处的加就负责节点的合并)

struct Node{
		int valSum;
		int valMax;
		int valMin;
		int lazy;
		Node operator+(Node n2){
				Node newNode;
				newNode.valSum = valSum + n2.valSum;
				newNode.valMax = max(valMax, n2.valMax);
				newNode.valMin = min(valMin, n2.valMin);
				return newNode;
		}
    Node operator+(int val){
				Node newNode;
				newNode.valSum += val;
				newNode.valMax += val;
				newNode.valMin += val;
				return newNode;
		}
}

线段树的构建

对于建立一个这样的空间，我们可以发现很多都是在做重复的工作，所以不妨使用递归。再从下往上构建，颇有回溯味道。再根据数组储存树的基础知识，获取左子节点的方法是 index * 2 右子节点是 index * 2 +1

void build(vector<Node> &a, int left, int right, int arrNo) {
	  if (left == right) {
		    arr[arrNo] = a[left];
		    return;
	  }
	  int mid = (left + right) / 2; // 当然你可以选择防溢出
	  
	  int leftTreeNo = arrNo * 2;
	  int rightTreeNo = arrNo * 2 + 1;
	  
	  build(a, left, mid, leftTreeNo);
	  build(a, mid + 1, right, rightTreeNo);
		// 特征值向上转移，这里使用相加，当然还可以使用其它方式
	  arr[arrNo] = arr[leftTreeNo] + arr[rightTreeNo];
}

线段树的区间查询

线段树的区间查询不一定是，这里我们以求和为例子，也就是arr[1]储存1~5所有值的和，每个元素管理的区间的区间特征值作为它的值。同样，你也可以使用结构体来代表一个节点，这样就可以储存多个值。

线段树的区间查询有一个特点，一次查询最后是两个节点的和。例如当我求区间[2, 5] 实际上访问的就是节点[2, 2]和[3, 5]两个节点的和并。

为什么是两个：已知如果是多个一定连续，如果两个连续大概率合并成一个。

所以对于区间查询来说，主要问题就是如何找到这两个节点。

Node getsum(int queryLeft, int queryRight, int nodeLeft, int nodeRight, int node) {
	  if (queryLeft <= nodeLeft && nodeRight <= queryRight)
	    return arr[node];
	  
	  int mid = (nodeLeft + nodeRight) / 2; // 当然你可以选择防溢出
	  int leftTreeNo = node * 2;
	  int rightTreeNo = node * 2 + 1;
	  Node sum = {0, MAX, MIN, 0};
	  
	  if (queryLeft <= mid) 
			  sum = sum + getsum(queryLeft, queryRight, nodeLeft, mid, leftTreeNo);
	  if (mid < queryRight) 
			  sum = sum + getsum(queryLeft, queryRight, mid + 1, nodeRight, rightTreeNo);
	  return sum;
}

通过递归从上往下去寻找即可。见上代码。

线段树的区间修改

根据简单的判断我们可以得出，线段树如果要修改一个值，就要同步修改上面的所有值，但如果修改一个区间，同样我们要进行很大的成本修改，对此，咱们提出了懒惰标级。

懒惰标记

懒惰标记的目的就是延迟对具体底下的值进行修改。例如我要修改的是区间[1, 3]的所有值，那我先只改[1, 2]和[3, 3]，如果我之后查询的是[1, 4] 和 [1, 5]那么实际上就没有必要落实到1和2个题元素上，那我们就把这个修改暂时留在[1, 2]的这个节点上，等到我真的要去查询[1, 1]或者[2, 2]，我再把这个修改下沉。

以下是关于懒惰标记的区间更新(区间增加或者区间减少)

void update(int queryLeft, int queryRight, int nodeLeft, int nodeRight, int node, int add) {
  if (queryLeft <= nodeLeft && nodeRight <= queryRight) {
		  arr[node] = arr[node] + (nodeRight - nodeLeft + 1) * add;
        
	    arr[node].lazy += add;
	    return;
  } 
  int mid = (nodeLeft + nodeRight) / 2;
  int leftTreeNo = node * 2;
  int rightTreeNo = node * 2 + 1;
  
  if (arr[node].lazy and nodeLeft != nodeRight) { // 向下转移懒惰标记
	    arr[leftTreeNo] = arr[leftTreeNo] + arr[node].lazy * (mid - nodeLeft + 1);
	    arr[rightTreeNo] = arr[rightTreeNo] + arr[node].lazy * (nodeRight - mid);
	    
	    arr[leftTreeNo].lazy += arr[node].lazy;
	    arr[rightTreeNo].lazy += arr[node].lazy;
	    
	    arr[node].lazy = 0;
  }
  
  if (queryLeft <= mid) 
		  update(queryLeft, queryRight, nodeLeft, mid, leftTreeNo, add);
  if (mid < queryRight) 
		  update(queryLeft, queryRight, mid + 1, nodeRight, rightTreeNo, add);
	
  arr[node] = arr[leftTreeNo] + arr[rightTreeNo];
}

以下是关于懒惰标记的区间查询

我们说过，一旦查询到下面，就需要对懒惰标记进行下移

Node getsum(int queryLeft, int queryRight, int nodeLeft, int nodeRight, int node) {
	  if (queryLeft <= nodeLeft && nodeRight <= queryRight)
	    return arr[node];
	  
	  int mid = (nodeLeft + nodeRight) / 2;
	  int leftTreeNo = node * 2;
	  int rightTreeNo = node * 2 + 1;
	  
	  if (arr[node].lazy and nodeLeft != nodeRight) { // 向下转移懒惰标记
	    arr[leftTreeNo] = arr[leftTreeNo] + arr[node].lazy * (mid - nodeLeft + 1);
	    arr[rightTreeNo] = arr[leftTreeNo] + arr[node].lazy * (nodeRight - mid);
	    
	    arr[leftTreeNo].lazy += arr[node].lazy;
	    arr[rightTreeNo].lazy += arr[node].lazy;
	    
	    arr[node].lazy = 0;
  }
	  
	  Node sum = {0, MAX, MIN, 0};
	  if (queryLeft <= mid) 
			  sum = sum + getsum(queryLeft, queryRight, nodeLeft, mid, leftTreeNo);
	  if (mid < queryRight) 
			  sum = sum + getsum(queryLeft, queryRight, mid + 1, nodeRight, rightTreeNo);
	  return sum;
}

当然也可以把对区间的操作从“都增加一个值add”变成“都变成一个值x”。

此时的lazy标签就代表要改的值了，但需要注意一点，主要另一个值来判断是否要修改，因为lazy标签为0时，代表的是全部值改为0而并不是不修改元素。

一些优化

在叶子节点处无需下放懒惰标记，所以懒惰标记可以不下传到叶子节点。
动态创建子节点，在不访问的时候就不创建节点。
标记永久化：如果确定懒惰标记不会在中途被加到溢出，那么就可以将标记永久化。标记永久化可以避免下传懒惰标记，只需在进行询问时把标记的影响加到答案当中，从而降低程序常数。也就是不需要修改子节点的值，只需要一直利用路途中的懒惰标记即可。

Mai Icy