暑假的救赎系列day3 注意注意！ k<<1 + 1 是cuowud 应该写成 (k << 1) + 1 其他没什么

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int sum[4*N],a[N],n,m;
void check()
{
	for(int i=1; i <= 10 ;i++)
	{
		cout << sum[i] << " ";
	}
	cout << endl;
}
void build(int k,int l,int r)
{
	if(l == r)
	{
		sum[k] = a[l];
		return;
	}
	int mid = (l+r )/ 2;
	build(k *2 , l,mid);
	build(k *2 + 1,mid+1,r);
	sum[k] = sum[k*2] + sum[k * 2 + 1];
}
int sm(int k,int l,int r,int s,int t)
{
	if( s <= l && r <= t)
	{
		return sum[k];
	}
	int mid = (l + r) /2 ;
	int ans = 0;
	if(mid >= s) ans += sm(k*2,l,mid,s,t);
	if(mid + 1 <= t) ans += sm(k*2+1,mid+1,r,s,t);
	return ans; 
}
void change(int k,int l,int r,int id,int x)
{
	if(l == r)
	{
		sum[k] = x;
		return;
	}
	int mid = (l + r) /2;
	if(mid >= id) change(k*2,l,mid,id,x);
	else change(k*2+ 1 ,mid + 1,r,id,x);
	sum[k] = sum[k*2] + sum[k *2 + 1];
}
int main()
{
	cin >> n>> m;
	for(int i=1; i <= n ;i++)
	{
		cin >> a[i];
	}
	build(1,1,n);
	for(int i=1; i <= m ;i++)
	{
		int op,l,r,x,y;
		cin >> op;
		if(op == 1) 
		{
			cin >> x >> y;
			change(1,1,n,x,y);
		}
		if(op == 2)
		{
			cin >> l >> r;
			cout << sm(1,1,n,l,r) << endl;
		}
	}
	return 0;
}

基础线段树习题

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 200005;
int n,m,k,s,t,opt,x,y;
int a[N];//线段树维护的原数组
struct Segment_Tree{
	#define mid (l+r>>1)
	int sum[N<<2];//存储线段树的区间和，空间记得开到4倍 
	void pushup(int p){//节点信息的向上合并 
		sum[p]=sum[p<<1]+sum[p<<1|1];
	}
	void build(int p,int l,int r){
		if (l==r) {//叶子节点，对应原数列的初始区间 
			sum[p]=a[l];
			return;
		}
		build(p<<1,l,mid);//建左子树 
		build(p<<1|1,mid+1,r);//建右子树 
		pushup(p);//把子树信息合并到当前点 
	}
	void change(int p,int l,int r,int s,int t){
		//当前区间的节点编号为p，表示区间为[l,r]
		//要修改的点为s，修改为t 
		if (l==r) {//找到了要修改的单点，直接修改 
			sum[p]=t;
			return; 
		}
		if (s<=mid) change(p<<1,l,mid,s,t);
		else change(p<<1|1,mid+1,r,s,t);
		//根据要修改的位置在左右子树里找 
		pushup(p); 
		//由于信息被修改了，所以最后要沿途更新线段树节点的信息 
	}
	int query(int p,int l,int r,int s,int t){
		//当前区间的节点编号为p，表示区间为[l,r]
		//要查询区间[s,t]中每个数的和 
		if (l>=s && r<=t) return sum[p];
		//如果当前区间已经被答案包含，直接计入答案 
		int ans=0;
		if (s<=mid) ans=query(p<<1,l,mid,s,t);
		if (t>mid) ans+=query(p<<1|1,mid+1,r,s,t);
		//往左右子树分开找 
		return ans; 
	}
}T; 
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for (int i=1;i<=n;++i) cin>>a[i];
	T.build(1,1,n);
	for (int i=1;i<=m;++i){
		cin>>opt>>x>>y;
		if (opt==1) T.change(1,1,n,x,y);
		else cout<<T.query(1,1,n,x,y)<<"\n";
	} 
}

#include <iostream>
#define MAXN 500010

using namespace std;

int n , m , a[ MAXN ] , sum[ MAXN * 4 ];

void build( int x , int l , int r )
{
//目前建立编号为x的节点，这个节点对应区间 [l,r]
if( l == r )
{
sum[x] = a[l];
return;
}
int mid = ( l + r ) / 2;
build( 2 * x , l , mid );
build( 2 * x + 1 , mid + 1 , r );
sum[x] = sum[2 * x] + sum[2 * x + 1];
}

void modify( int x , int l , int r , int s , int t )
{
//目前递归到编号为x的节点，这个节点对应区间 [l,r]，我要把a[s]的值修改为t
if( l == r )
{
//递归到叶子了，编号为x的节点的sum对应a[s]的值
sum[x] = t;
return;
}
int mid = ( l + r ) / 2;
if( s <= mid )
{
modify( 2 * x , l , mid , s , t );
}
else
{
modify( 2 * x + 1 , mid + 1 , r , s , t );
}
sum[x] = sum[2 * x] + sum[2 * x + 1];
}

int find( int x , int l , int r , int s , int t )
{
//目前递归到了编号为x的节点，这个节点对应区间 [l,r]，我询问的区间是 [s,t]
if( s <= l && r <= t )
{
return sum[x];
}
int ans = 0 , mid = ( l + r ) / 2;
if( s <= mid )
{
ans += find( 2 * x , l , mid , s , t );
}
if( t >= mid + 1 )
{
ans += find( 2 * x + 1 , mid + 1 , r , s , t );
}
return ans;
}

int main()
{
cin >> n >> m;
for( int i = 1 ; i <= n ; i++ )
cin >> a[i];
build( 1 , 1 , n );
while( m-- )
{
int opt , s , t;
cin >> opt >> s >> t;
if( opt == 1 )
{
modify( 1 , 1 , n , s , t );
}
else
{
cout << find( 1 , 1 , n , s , t ) << endl;
}
}
return 0;
}