数列操作 线段树 C++

解题思路:

    线段树的基础操作，线段树的特点是左右子节点管理父节点的管理区间的一半。

    查询思路:如果查询区间完全覆盖了当前节点管理的区间，则直接返回；否则判断是否与子节点管理区间有

交集，如果有则递归判断。

    建树和更新思路:当我们更新某个节点值时(建树可以看作将叶子节点更新)，最终都会更新根节点，

所以实现时可以以根作为递归入口，更新其子节点后再更新自己。
注意事项:

    线段树的大小一半取2n左右  详细见https://www.luogu.com.cn/discuss/show/52150

参考代码:

/*
 *数列操作:线段树
 *!!线段树下标从1开始 
 */
#include<cstdio>

const int Max_N = 100000;

int n,m;
int a[Max_N+1];
int tree[(Max_N<<2)+1];

void build(int k, int l, int r); //建立线段树 
int  query(int L, int R, int k, int l, int r); //查询 
void updatePoint(int p, int v, int k, int l, int r); //更新点 
void pushUp( int k );  //向上更新 

int main()
{
	scanf("%d%d",&n,&m);
	for( int i=1; i<=n; i++ )	scanf("%d",&a[i]);
	
	build(1,1,n);
	
	while( m-- )
	{
		int k,l,r;
		scanf("%d%d%d",&k,&l,&r);
		if( k==0 )
		{
			printf("%d\n",query(l,r,1,1,n)); 
		}
		else
		{
			updatePoint(l,r,1,1,n);
		}
	}
	
	return 0;
} 

void build(int k, int l, int r)
{
	if( l==r )
	{
		tree[k] = a[l];
	}
	else
	{
		int m = l + ((r-l)>>1);
		build(k<<1,l,m);
		build(k<<1|1,m+1,r);
		pushUp(k);
	}
}

void pushUp(int k)
{
	tree[k] = tree[k<<1] + tree[k<<1|1];
}

void updatePoint(int p, int v, int k, int l, int r)
{
	if( l==r )
	{
		tree[k] += v;
	}
	else
	{
		int m = l + ((r-l)>>1);
		if( p<=m )
			updatePoint(p,v,k<<1,l,m);
		else
			updatePoint(p,v,k<<1|1,m+1,r);
		pushUp(k);
	}
}

int query(int L, int R, int k, int l, int r)
{
	if( L<=l && r<=R )
	{
		return tree[k];
	}
	else
	{
		int m = l + ((r-l)>>1);
		int res = 0;
		if( L<=m && R>=l )
			res += query(L,R,k<<1,l,m);
		if( L<=r && R>m )
			res += query(L,R,k<<1|1,m+1,r);
		return res;
	}
}