树状数组是线段树的一种特殊情况,对于特殊情况用树状数组会更简单。
数组数组详细:http://blog.csdn.net/gladyoucame/article/details/11881399
此题线段树的解法:http://blog.csdn.net/gladyoucame/article/details/9293357
定义一个函数Lowbit(Int):Int,返回对参数转为二进制后,将最后一个1进位的结果.
这段代码可以简单的理解为是树状数组向前或向后衍生是用的。
向后主要是为了找到目前节点的父节点,比如要将C[4]+1,那么4+(4&(-4))=8,C[8]+1,8+(8&(-8))=16,
C[16]+1。
向前主要是为了求前缀和,比如要求A[1]+...+A[12]。那么,C[12]=A[9]+...+A[12];然后12-12&(-12)=8,
C[8]=A[1]+...+A[8]。
#include <iostream>
#include <stdio.h>
using namespace std;
const int MAX = 50000;
//
#define lowbit(x) ((x)&(-x)) //或 x and (x or (x - 1));
int com[MAX + 1], N, T;
//修改位置pos处的值, 增量为va
void modify(int pos, int val) {
while (pos <= N) {
com[pos] += val;
pos = pos + lowbit(pos);
}
}
//查询
int quy(int x) {
int sum = 0;
while (x > 0) {
sum = sum + com[x];
x = x - lowbit(x);
}
return sum;
}
int main()
{
while (scanf("%d", &T) != EOF) {
int ca = 1, x, y;
while (T--) {
printf("Case %d:\n", ca++);
scanf("%d", &N);
for (int i = 0; i <= N; ++i)
com[i] = 0;
for (int i = 1; i <= N; ++i) {
scanf("%d", &x);
modify(i, x);
}
char ask[10];
while (scanf("%s", ask), ask[0] != 'E') {
scanf("%d%d", &x, &y);
switch (ask[0]) {
case 'A':
modify(x, y);
break;
case 'S':
modify(x, -y); //值减少,所以为负
break;
case 'Q':
printf("%d\n", quy(y) - quy(x - 1));
break;
}
}
}
}
return 0;
}
分享到:
相关推荐
2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。
算法-确定比赛名次(HDU-1285).rar
考试类精品--A simple SDK for HDU. 一个提供一卡通服务、考试、课表、选课和公共信息等 API
算法-母牛的故事(HDU-2018)(包含源程序).rar
算法-畅通工程续(HDU-1874)(包含源程序).rar
算法-超级赛亚ACMer(HDU-5246)(包含源程序).rar
hdu 1166线段树代码
HDU 里面的2000~2099道题目的源码。谢谢支持
题面 【题目描述】 有nnn个营地,已知每个营地的人数,有四条命令: (1)Add(1) Add(1)Add iii jjj,iii和jjj为正整数,表示第iii个营地增加jjj个人(jjj不超过303030) (2)Sub(2)Sub(2)Sub iii jjj ,iii和jjj为正...
杭电ACM2000-2099题的解题报告
hdu 1166线段树
基础算法类 ACM 入门 杭电OJ 11页题目题解,算法入门的时候刷题可以参考 搜集整理起来了比单个去搜题解方便快捷
杭电acm解题报告 详细解析2000-2099 适合acm初学者
hdu 1005.比较简单的一道题,有兴趣的可以看看。
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
算法-数塔(HDU-2084).rar
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
算法-欧拉回路(HDU-1878)(包含源程序).rar