给定一个长度为n（n<=100000），初始值都为0的序列，x(x<=10000)次的修改某些位置上的数字，每次加上一个数，然后提出y (y<=10000)个问题，求每段区间的和。时间限制1秒。
输入格式：
第一行1个数，表示序列的长度n
第二行1个数，表示操作的次数w
后面依次是w行，分别表示加入和询问操作
其中，加入用x表示，询问用y表示
x的格式为"x a b" 表示在序列a的位置加上b
y的格式为"y a b" 表示询问a到b区间的加和
输出格式：
每行一个数，分别是每次询问的结果
输出样例#1： 8 17
线段树中最低级的模板，只有区间查询和单点修改。
请放心食用。
#include <iostream> #include <cstring> #include <cstdio> #define MAXN 100007 #define lson (k<<1) #define rson (k<<1)+1 #define int long long using namespace std; int n, m, a, b, Ans; char c; struct node { int l, r; int sum; }tree[MAXN*4]; void build(int k, int ll, int rr) { tree[k].l = ll, tree[k].r = rr; if(ll == rr) { tree[k].sum = 0; return ; } int mid = (ll+rr)/2; build(lson, ll, mid); build(rson, mid+1, rr); tree[k].sum = tree[lson].sum+tree[rson].sum; } void change(int k) { if(tree[k].l == tree[k].r && tree[k].l == a) { tree[k].sum += b; return ; } int mid = (tree[k].l+tree[k].r)/2; if(mid >= a) change(lson); if(mid < a) change(rson); tree[k].sum = tree[lson].sum+tree[rson].sum; } void find(int k) { if(tree[k].l >= a && tree[k].r <= b) { Ans += tree[k].sum; return ; } int mid = (tree[k].l+tree[k].r)/2; if(mid >= a) find(lson); if(mid < b) find(rson); } main() { scanf("%lld%lld", &n, &m); build(1, 1, n); for(int i=1; i<=m; i++) { Ans = 0; cin>>c>>a>>b; if(c == 'x') { change(1); } else { find(1); printf("%lld\n", Ans); } } }
转载于:https://www.cnblogs.com/bljfy/p/9126823.html
相关资源：数据结构—成绩单生成器