线段树

线段树/区间树（Segment tree）是一种二叉搜索树：

特点：

• 每个结点表示的是一个线段，或者说是一个区间。
• 当父节点的区间为$[x, y]$时，左孩子的区间就为$[x, \frac{ (x + y) }{ 2 }]$，右孩子的区间就为$[\frac{ (x + y) }{ 2 } + 1, y]$。
• 对于每一棵线段树上的节点，都有三个值：左区间、右区间以及权值。
  （在某些情况下只有左右区间，这个时候线段树只是作为维护某个值而使用的数据结构，如扫描线）

线段树主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为 O(logN）。而未优化的空间复杂度为 2N，因此有时需要离散化来压缩空间。

模版

class SegmentTree {
	class Node {
		int left, right;// 左右区间的值
		boolean cover;// 表示是否被覆盖
		int count;// 表示此节点表示的线段区间出现的次数（被覆盖的次数），默认为0
		Node leftChild, rightChild;

		Node(int left, int right) {
			this.left = left;
			this.right = right;
			this.count = 0;
			this.cover = false;
		}
	}

	Node root;

	/**
	 * 建立一棵线段树
	 * 
	 * @param left 左区间
	 * @param right 右区间
	 */
	void build(int left, int right) {
		root = new Node(left, right);
		build(root);
	}

	/**
	 * 建立一棵线段树
	 * 
	 * @param root 根节点
	 */
	void build(Node root) {
		int left = root.left;
		int right = root.right;
		// root节点为叶子节点
		if (right - left == 1) {
			return;
		} else if (right - left > 1) {
			int mid = (left + right) >> 1;//// 将左右区间平分
			Node leftNode = new Node(left, mid);
			Node rightNode = new Node(mid, right);
			root.leftChild = leftNode;
			root.rightChild = rightNode;
			// 递归的创建左右子树
			build(leftNode);
			build(rightNode);
		}
	}

	/**
	 * 插入一条线段[left, right]
	 * 
	 * @param left 左端点
	 * @param right 右端点
	 */
	void insert(int left, int right) {
		insert(left, right, root);
	}

	/**
	 * 插入一条线段[left, right]
	 * 
	 * @param left 左端点
	 * @param right 右端点
	 * @param node 节点
	 */
	void insert(int left, int right, Node node) {
		if (node == null || left < node.left || right > node.right) {
			System.out.println("输入的参数不合法!" + "left:" + left + " " + "right:" + right);
			System.out.println("root:" + node.left + " " + node.right);
			return;
		}
		if (node.left == left && node.right == right) {
			node.count++;
			node.cover = true;
			return;
		}
		int mid = (node.left + node.right) >> 1;
		if (right <= mid) {
			insert(left, right, node.leftChild);
		} else if (left >= mid) {
			insert(left, right, node.rightChild);
		} else {
			insert(left, mid, node.leftChild);
			insert(mid, right, node.rightChild);
		}
	}

	/**
	 * 删除一条线段[left, right]
	 * 
	 * @param left 左端点
	 * @param right 右端点
	 */
	void delete(int left, int right) {
		delete(left, right, root);
	}

	/**
	 * 删除一条线段[left, right]
	 * 
	 * @param left 左端点
	 * @param right 右端点
	 * @param node 节点
	 */
	void delete(int left, int right, Node node) {
		if (node == null || left < node.left || right > node.right) {
			System.out.println("输入的参数不合法!");
			return;
		}
		if (left == node.left && right == node.right) {
			node.count--;
			if (node.count == 0) {
				node.cover = false;
			}
			return;
		}
		int mid = (node.left + node.right) >> 1;
		if (right <= mid) {
			delete(left, right, node.leftChild);
		} else if (left >= mid) {
			delete(left, right, node.rightChild);
		} else {
			delete(left, mid, node.leftChild);
			// 注意不是mid+1，比如区间[1, 10]的左右两部分分别是[1, 5]，[5, 10]
			delete(mid, right, node.rightChild);
		}
	}

	/**
	 * 前序遍历
	 */
	void preOrder() {
		preOrder(root);
	}

	/**
	 * 前序遍历
	 * 
	 * @param root 根节点
	 */
	void preOrder(Node root) {
		if (root.right - root.left == 1) {
			System.out.println("[" + root.left + "," + root.right + "]:" + root.count);
			return;
		} else if (root.right - root.left > 1) {
			System.out.println("[" + root.left + "," + root.right + "]:" + root.count);
			preOrder(root.leftChild);
			preOrder(root.rightChild);
		}
	}

	/**
	 * 统计线段树中cover为true的线段的总长度
	 */
	int count() {
		return count(root);
	}

	/**
	 * 统计线段树中cover为true的线段的总长度
	 * 
	 * @param node 节点
	 */
	int count(Node node) {
		if (node.cover == true) {// 不继续往下查找，否则会重复
			return node.right - node.left;
		} else {
			if (node.right - node.left == 1) {
				return 0;
			} else {
				return count(node.leftChild) + count(node.rightChild);
			}
		}
	}
}

优点

• 时间快，操作多

线段树的所有操作都是基于分治算法，再经过 pushUp 优化，整个算法十分稳定。比起一般的数组暴力算法，线段树是明显更优的。

结构	修改	求和	平均
线段树	O(logN)	O(logN)	O(logN)
前缀和	O(N)	O(1)	O(N/2)
普通	O(1)	O(N)	O(N/2)

另外，它操作多样化，比起树状数组，多了区间最值一种操作。　　

缺点

• 浪费空间

线段树一直是一棵满二叉树，所以无论如何，它所开的空间必须是四倍。
但是在某些情况，线段树会浪费三倍的空间(只有一条链等)，但你又不能省掉这三倍空间，还是得苦逼的开四倍。

和树状数组比起来，一棵普通的线段树是树状数组空间的四倍。