今天讲一下一些关于线段树的知识以及它的各种区间操作（基于Java语言的哦）

这是鼠鼠我平时打算法竞赛打的一些线段树的代码，希望不喜勿喷，如果能够给你带来帮助，那是俺的荣幸！说完这章，等我有空就讲一下一些线段树的题解哈

一、概念

线段树，类似区间树，是一个完全二叉树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(logn)。

线段树的每个节点表示一个区间，子节点则分别表示父节点的左右半区间，例如父亲的区间是[a,b]，那么(c=(a+b)/2)左儿子的区间是[a,c]，右儿子的区间是[c+1,b]。

大概这么个意思，概念不多讲（太菜）：

                                                            （字有亿点丑） 

二、线段树建立

利用tree[]数组存储线段树，tree[x]的左子树为tree[x*2],右子树为tree[p*2+1]。（如果咱还要计算区间最大最小时可以把maxn[]、minn[]定义上去，直接上代码啦）

private static void build(int p,int l,int r) {
		if(l == r) {
			tree[p] = maxn[p] = minn[p] = num[l];//全部赋值上
			return ;
		}
		int mid = (l+r)/2;
		build(p*2,l,mid);
		build(p*2+1,mid+1,r);
		tree[p] = tree[p*2] + tree[p*2+1];
		maxn[p] = Math.max(maxn[p*2], maxn[p*2+1]);
		minn[p] = Math.min(minn[p*2], minn[p*2+1]);
	}

三、线段树的push_down方法:

因为后面的查询以及修改用到这个延迟标记，所以先说说它。先将要修改的存进数组内，待查找时就可以将数据再算上，可以省时间（比如先+1 再+2 可以先存着，延迟标志，然后查询时一口气+3的道理）（这里定义一个数组，貌似挺多人叫懒惰数组，lazy[]，用来存待计算的数据）

一、区间加法的push_down()方法: 

private static void push_down(int node,int l,int r) {//加法的push()方法
		if(lazy[node] > 0) {
			int mid = (l+r)/2;
			lazy[node*2]+=lazy[node];//将要加的数据加入左右子树的待加数组。
			lazy[node*2+1]+=lazy[node];
			tree[node*2]+=(lazy[node]*(mid-l+1));//将lazy数组中的数据加入到tree数组就ok
			tree[node*2+1]+=(lazy[node]*(r - mid));
			lazy[node] = 0;//加完后，直接清零
		}
	}

二、乘法的push_down()方法：

lazy[]，要先定义为1。乘1还是原来的数嘛。

private static void push_down(int node,int l,int r) {//和加法差不多耶
		if(lazy[node]!=1) {
			int mid = (l+r)/2;
			lazy[node*2]*= lazy[node];
			lazy[node*2+1]*=lazy[node];
			tree[node*2] *= lazy[node];
			tree[node*2+1]*= lazy[node];
			lazy[node] = 1;
		}
	}

三、如果加法、乘法都有，可以这么改

定义两个懒惰数组，la1[]、la2[]代表加和乘，那么加法的数组在push时也要乘一下，举个栗子，加10再乘2，不就是加上20咩。这么个道理,而乘法则不会受到加法的影响。

	private static void push_down(int p,int x,int y) {
		if(x == y) {
			return ;
		}
		int mid = (x+y)/2;
		tree[p*2] = tree[p*2]*la1[p] + la2[p]*(mid-x+1);
		tree[p*2+1] = tree[p*2+1]*la1[p] + la2[p]*(y - mid);
		la1[p*2] = la1[p*2] * la1[p];
		la1[p*2+1] = la1[p*2+1] * la1[p];
		la2[p*2] = la2[p*2]*la1[p] + la2[p];
		la2[p*2+1] = la2[p*2+1]*la1[p] + la2[p];
		la1[p] = 1;
		la2[p] = 0;
	}

ok,说完了push开始讲查询

四、线段树的查询：        一、单点查询：

       很简单，直接递归查询就ok。

private static int findone(int p,int l,int r,int pi) {
		if(pi == l && pi == r) {
			return tree[p];//如果查的是此时的点的内容，返回它
		}
		int mid = (l+r)/2;
		push_down(p,l,r);
		if(pi <= mid) {//在左子树
			return findone(p*2,l,mid,pi);
		}
		else {//在右子树
			return findone(p*2+1,mid+1,r,pi);
		}
	}

        二、区间查询之查区间和：

private static int query(int p,int l,int r,int x,int y) {
		if(x <= l && r <= y) {//在待查区间的内部，返回tree[p];
			return tree[p];
		}
		if(l > y || x > r) {//两者无交集了，直接return 0；
			return 0;
		}
		int mid = (l+r)/2;
		push_down(p,l,r);//博客上说了
		return query(p*2,l,mid,x,y) + query(p*2+1,mid+1,r,x,y);
	}

       三、区间查询之找区间最大值

设置区间的最大值（最小值）数组，然后递归时，每次都找一下然后比较大小返回，思路很简单。

private static int findmax(int p,int l,int r,int x,int y) {
		if(x <= l && r <= y) {
			return maxn[p];
		}
		int mid = (l+r)/2;
		int maxx = Integer.MIN_VALUE;
		if(mid >= x) {
			maxx = Math.max(maxx, findmax(p*2,l,mid,x,y));
		}
		if(mid < y) {
			maxx = Math.max(maxx,findmax(p*2+1,mid+1,r,x,y));
		}
		return maxx;
	}

        四、区间查询之找区间最小值

private static int findmin(int p,int l,int r,int x,int y) {
    	if(x <= l && r <= y) {
			return minn[p];
		}
		int mid = (l+r)/2;
		int minn = Integer.MAX_VALUE;
		if(mid >= x) {
			minn = Math.min(minn, findmin(p*2,l,mid,x,y));
		}
		if(mid < y) {
			minn = Math.min(minn,findmin(p*2+1,mid+1,r,x,y));
		}
		return minn;
	}

五、线段树之修改更新      一、单点修改

很简单、递归找到这个点，直接改

private static void updateone(int p,int l,int r,int pi,int add) {
		if( l == pi && r == pi) {
			num[pi]+=add;
			tree[p] = num[pi];
			return;
		}
		int mid = (l+r)/2;
		if(mid >= pi) {
			updateone(p*2,l,mid,pi,add);
		}
		else {
			updateone(p*2+1,mid+1,r,pi,add);
		}
		tree[p] = tree[p*2]+tree[p*2+1];
	}

   二、区间修改

和区间查询的差不多，代码主要是对区间进行加法修改，乘法的话其实就是换成乘，差不多

private static void updateadd(int p,int l,int r,int x,int y,int add) {
		if(x<= l && r<=y) {
			tree[p] += (r-l+1)*add;//区间内每个数加add,相当于区间和加上add*(r-l+1)
			lazy[p]+=add;//保存一下
			return ;
		}
		push_down(p,l,r);//延迟标记
		int mid = (l+r)/2;
		if(mid >= x) {
			updateadd(p*2,l,mid,x,y,add);
		}
		if(mid < y) {
			updateadd(p*2+1,mid+1,r,x,y,add);
		}
		tree[p] = tree[p*2] + tree[p*2+1];
	}

ok,接下来我把完整的代码模板发出来，已经测试过的。

import java.util.*;
import java.io.*;
public class 线段树各种操作 {
	private static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	private static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	private static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static String Line() {
		String a = "";
		try {
			a = bf.readLine();
		} catch (IOException e) {
			// TODO 自动生成的 catch 块
			e.printStackTrace();
		}
		return a;
	}
	private static int Int() {
	try {
		st.nextToken();
	} catch (IOException e) {
		// TODO 自动生成的 catch 块
		e.printStackTrace();
	}
	return (int)st.nval;
	}
	//首先建立线段树
	private static void build(int p,int l,int r) {//建树
		if(l == r) {
			tree[p] = maxn[p] = minn[p] = num[l];
			return ;
		}
		int mid = (l+r)/2;
		build(p*2,l,mid);
		build(p*2+1,mid+1,r);
		tree[p] = tree[p*2]+tree[p+2+1];
		maxn[p] = Math.max(maxn[p*2], maxn[p*2+1]);
		minn[p] = Math.min(minn[p*2], minn[p*2+1]);
	}
	//建线段树
	
	//单点查询
	private static int findone(int p,int l,int r,int pi) {
		if(pi == l && pi == r) {
			return tree[p];//如果查的是此时的点的内容
		}
		int mid = (l+r)/2;
		if(pi <= mid) {
			return findone(p*2,l,mid,pi);
		}
		else {
			return findone(p*2+1,mid+1,r,pi);
		}
	}
	//单点查询
	
	//区间查询和
	private static int findsum(int p,int l,int r,int x,int y) {
		if(x<= l && r <= y) {
			return tree[p];
		}
		if(l > y || x > r) {
			return 0;
		}
		int mid = (l+r)/2;
		return findsum(p*2,l,mid,x,y) + findsum(p*2+1,mid+1,r,x,y);
	}
	//区间查询和
	
	//区间查询最小值
	private static int findmin(int p,int l,int r,int x,int y) {
		if(x <= l && r <= y) {
			return minn[p];
		}
		int res = Integer.MAX_VALUE;
		int mid = (l+r)/2;
		if(mid >= x) {
			res = Math.min(res, findmin(p*2,l,mid,x,y));
		}
		if(mid < y) {
			res = Math.min(res, findmin(p*2+1,mid+1,r,x,y));
		}
		return res;
	}
	//区间查询最小值
	
	//区间查询最大值
	private static int findmax(int p,int l,int r,int x,int y) {
		if(x<= l && r <= y) {
			return maxn[p];
		}
		int res = Integer.MIN_VALUE;
		int mid = (l+r)/2;
		if( mid >= x) {
			res = Math.max(res, findmax(p*2,l,mid,x,y));
		}
		if( mid < y) {
			res = Math.max(res, findmax(p*2+1,mid+1,r,x,y));
		}
		return res;    
	}
	//区间查询最大值
	
	//单点修改
	private static void updateone(int p,int l,int r,int pi,int val) {
		if(l == pi && r == pi) {
			tree[p] = maxn[p] = minn[p] = num[pi] = val;
			return ;
		}
		int mid = (l+r)/2;
		if(mid >= pi) {
			updateone(p*2,l,mid,pi,val);
		}
		else {
			updateone(p*2+1,mid+1,r,pi,val);
		}
		tree[p] = tree[p*2]+tree[p*2+1];
		maxn[p] = Math.max(maxn[p*2],maxn[p*2+1]);
		minn[p] = Math.min(minn[p*2], minn[p*2+1]);
	}
	//单点修改
	
	//区间修改、加法
	private static void updateadd(int p,int l,int r,int x,int y,int add) {
		if(x <= l && r <= y) {
			tree[p] += (r-l+1)*add;
			return ;
		}
		int mid = (l+r)/2;
		if(mid >= x) {
			updateadd(p*2,l,mid,x,y,add);
		}
		if(mid < y) {
			updateadd(p*2+1,mid+1,r,x,y,add);
		}
		tree[p] = tree[p*2] + tree[p*2+1];
		maxn[p] = Math.max(maxn[p*2],maxn[p*2+1]);
		minn[p] = Math.min(minn[p*2],minn[p*2+1]);
	}
	//区间修改、加法
	
	
	private static int tree[],num[];
	private static int maxn[];//保存最大值
	private static int minn[];//保存最小值
	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		//根据实际情况改一改。
	}
}

ok,结束，祝大家学有所成！接下来等有空更新一些例题。