HDU 1166-敌兵布阵
题意:
给一个数组,有查询、增加、减少三种操作 对于每次询问 输出从i到j所有元素的和
思路:树状数组裸题
特别的 对于减少操作 只需向x位置更新-y即可
#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<map>
#include<vector>
#include<set>
#include<algorithm>
#include<vector>
#include<utility>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define lowbit(e) ((e)&-(e))
#define mem(n,a) memset(n,a,sizeof(n))
#define rep(i,be,en) for(int i=be;i<=en;++i)
#define pre(i,be,en) for(int i=en;i>=be;--i)
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b); }
using namespace std;
typedef long long ll;
const int N = 5e4 + 10;
int bitree[N];
void update(int x, int y, int n) {
//单点更新
for (int i = x;i <= n;i += lowbit(i)) {
bitree[i] += y;
}
}
int getsum(int x) {
// 区间求和
int ans = 0;
for (int i = x;i;i -= lowbit(i)) {
ans += bitree[i];
}
return ans;
}
int main() {
int t;cin >> t;
for (int i = 1;i <= t;++i) {
int n;cin >> n;
for (int i = 1;i <= n;++i)bitree[i] = 0;
for (int j = 1;j <= n;++j) {
int val;scanf("%d", &val);
update(j, val, n);
}
printf("Case %d:\n", i);
while (1) {
string s;cin >> s;
if (s[0] == 'E')break;
int x, y;scanf("%d%d", &x, &y);
if (s[0] == 'Q') {
printf("%d\n", getsum(y) - getsum(x - 1));
}
else if (s[0] == 'A')update(x, y, n);
else update(x, -y, n);
}
}
return 0;
}