[数据结构与算法]线段树的查询与单点修改与建树

#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
int a[20]={},b[20];

inline void push(int xb)//将子节点的两个值上传
{
	b[xb]=b[xb*2]+b[xb*2+1];
}

inline void  build(int l,int r,int xb)//xb是下标
{
	if (l==r)//找到子节点，存下来并退出
	{
		b[xb]=a[l];return;
	}
	build(l,(l+r)/2,xb*2);//处理左边
	build((l+r)/2+1,r,xb*2+1);//处理右边
	push(xb);//处理好子节点后记得上传父亲节点
}

inline void dandian(int pos,int val,int l,int r,int xb)//xb是下标
{
	if (l==r)
	{
		b[xb]=val;return;//修改
	}
	int m=(l+r)/2;
	if  (m>=pos) dandian(pos,val,l,m,xb*2);//在左边就处理左边
	else dandian(pos,val,m+1,r,xb*2+1);//在右边就处理右边
	push(xb);//改完值后要记得改父亲节点
}

inline int  query(int ll,int rr,int l,int r,int xb){
	if (ll<=l&&rr>=r){return b[xb];}//若要找的区间比现在的区间大，直接返回值即可
	int m=(l+r)/2;
	int ans=0;
	if (rr>m) ans=ans+query(ll,rr,m+1,r,xb*2+1);//因为m没有等于m+1，所有这里是>号。若右边有要找的区间，就找右边
	if (ll<=m) ans=ans+query(ll,rr,l,m,xb*2);//若左边有要找的区间，就找左边
	return ans;
}

int main()
{
	int n,m,ll,rr,pos,val,p;
	cin >> n >> m;
	for (int i=1;i<=n;i++) cin >> a[i];
    build(1,n,1);//先输入a[i]才能建树
	for (int i=1;i<=m;i++)
	{
		cin >> p;
		if (p==1)//p=1是查询
		{
			cin >> ll >> rr;
			cout << query(ll,rr,1,n,1) << endl;
		}
		if (p==2)//p=2是单点修改
		{
			cin >> pos >> val;//pos是位置，val是要更改成的值
			dandian(pos,val,1,n,1);
		}
	}
}