线段树是一种基于分治思想的二叉树结构，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。通过构建线段树，可以在对数时间复杂度内对任意区间进行查询和修改操作。

#include<iostream>
using namespace std;
const int N = 5e5+7;
int n = 8,m,s,t;
int ans;
int a[N] = {0, 4, 5, 6, 2, 1, 3, 7, 8};
struct node{
	int r,l,sum,lazy;
}tree[N*4];
void push_down(int rt)
{
	int &x = tree[rt].lazy;
	if(x)
	{
		tree[rt<<1].lazy += x, 	tree[rt<<1|1].lazy += x;
		tree[rt<<1].sum += (tree[rt<<1].r - tree[rt<<1].l + 1) * x;
		tree[rt<<1|1].sum += (tree[rt<<1|1].r - tree[rt<<1|1].l + 1) * x;
		x = 0;
	}
}
void build(int l, int r, int rt)
{
	tree[rt].l = l,tree[rt].r = r,tree[rt].lazy = 0;
	if(r==l)
	{
		tree[rt].sum = a[l];
		return ;
	}
	int mid =(l+r)>>1;
	build(l, mid, rt<<1);
	build(mid+1, r, rt<<1|1);
	tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
}
void update(int rt, int pos, int val)
{
	int l = tree[rt].l, r = tree[rt].r;
	if(l == r) 	{
		tree[rt].sum+=val;
		return ;
	}
	int mid = (l+r)>>1;
	if(pos <= mid)
		update(rt<<1, pos, val);
	else
		update(rt<<1|1, pos, val);
	tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
}
void add(int l, int r, int rt, int val)
{
	int L = tree[rt].l, R = tree[rt].r;
	if(l <= L && r >= R)
	{
		tree[rt].sum += val;
		tree[rt].lazy += val;
		return ;
	}
	/**/push_down(rt)/**/;
	int mid = (L+R) >>1;
	if(l <= mid) add(l, r, rt<<1, val);
	if(r > mid) add(l, r, rt<<1|1, val);
	tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
}
int search(int l, int r, int rt)
{
	if(l <= tree[rt].l && r >= tree[rt].r)
	{
    	return tree[rt].sum;
	}	
	/**/push_down(rt);/**/
	int mid = (tree[rt].l + tree[rt].r) >> 1, res = 0 ;
	if(l <= mid) res += search(l, r, rt<<1);
	if(r > mid) res += search(l, r, rt<<1|1);
	return res;
}

int main(){

	build(1,n,1);
	update(1,5,1);
	add(1,2,1,2);
	cout<<search(1,8,1)<<endl;
	return 0;
}