线段树 区间修改 单点查询

请先阅读上一篇Bolg

算法思想

代码实现

Code

#include<bits/stdc++.h>
#define maxn 1000010
#define mid ((l+r)>>1)
#define li i<<1
#define ri 1+(i<<1)
using namespace std;

int n,val[maxn];

struct Node{
	int l,r,sum,k;
}tree[maxn];

void Read(){
	cin >> n;
	for(int i = 1;i <= n;i++)cin >> val[i];
}

void build(int i,int l,int r){
	tree[i].l = l;
	tree[i].r = r;
	if(l == r){
		tree[i].sum = val[l];
		return ;
	}
	build(li,l,mid);
	build(ri,mid+1,r);
	tree[i].sum = tree[li].sum + tree[ri].sum;
	return ;
}

void add(int i,int l,int r,int k){
	if(l <= tree[i].l && tree[i].r <= r){
		tree[i].k += k;
		return ;
	}
	if(tree[li].r >= l)
		add(li,l,r,k);
	if(tree[ri].l <= r)
		add(ri,l,r,k);
}

int search(int i,int dis,int ans){
	if(tree[i].l == tree[i].r){
		return val[dis] + tree[i].k;
	}
	if(dis <= tree[li].r)
		return tree[i].k + search(li,dis,ans);
	if(dis >= tree[ri].l)
		return tree[i].k + search(ri,dis,ans);
}

void interaction(){
	while(1){
		int tot;
		cin >> tot;
		if(tot == 1){
			int dis;
			cin >> dis;
			cout << search(1,dis,0) << endl;
		} else if(tot == 2){
			int l,r,k;
			cin >> l >> r >> k;
			add(1,l,r,k);
		} else if(tot == 3){
			return ;
		}
	}
}

int main(){
	cout << "query point" << endl << "change section" << endl;
	Read();
	build(1,1,n);
	cout << "query 1" << endl << "change 2" << endl << "break 3" << endl;
	interaction();
	return 0;
}

[c++]线段树 区间修改 单点查询

原文：https://www.cnblogs.com/rosyr050301/p/Segment_tree_2.html