AizuOJ DSL_2_B Range Sum Query (RSQ) （线段树）

source:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B
solution：用线段树维护区间和

#include 
using namespace std;
#define Mid ((l+r)>>1)
#define lson rt<<1,l,Mid
#define rson rt<<1|1,Mid+1,r
int sum[100005 << 2];void build(int rt, int l, int r)
{if (l == r)sum[rt] = 0;else {build(lson);build(rson);sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}
}void updata(int rt, int l, int r, int pos, int num)
{if (l == r && r == pos)sum[rt] += num;else{if (pos <= Mid)updata(lson, pos, num);else updata(rson, pos, num);sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}
}int query(int rt, int l, int r, int L, int R){if (l >= L && r <= R)return sum[rt];else{int tmp = 0;if (L <= Mid)tmp += query(lson, L, R);if (R > Mid)tmp += query(rson, L, R);return tmp;}
}int main(){int n, q, ch, x, y;scanf("%d %d", &n, &q);build(1,1,n);while (q--){scanf("%d%d%d", &ch, &x, &y);if (ch)printf("%d\n", query(1, 1, n, x, y));else updata(1, 1, n, x, y);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！