hdu1166(线段树单点更新&区间求和模板)
2024-09-05 20:32:53
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1166
题意:中文题诶~
思路:线段树单点更新,区间求和模板
代码:
#include <iostream>
#include <stdio.h>
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
using namespace std; const int MAXN = 5e4 + ;
int sum[MAXN << ]; void push_up(int rt){//向上求和
sum[rt] = sum[rt << ] + sum[rt << | ];
} //建树
void build(int l, int r, int rt){//sum[rt] 对应区间 [l, r] 的和
if(l == r){
scanf("%d", &sum[rt]);
return;
}
int mid = (l + r) >> ;
build(lson);
build(rson);
push_up(rt);//向上更新节点
} //单点更新
void updata(int p, int add, int l, int r, int rt){//在p点增加add
if(l == r){//找到p点
sum[rt] += add;//单点更新
return;
}
int mid = (l + r) >> ;
if(p <= mid) updata(p, add, lson);
else updata(p, add, rson);
push_up(rt);//向上更新节点
} //区间求和
int query(int L, int R, int l, int r, int rt){//对[L, R]区间求和
if(L <= l && R >= r) return sum[rt];//当前区间[l, r]包含在求和区间[L, R]中
int ans = ;
int mid = (l + r) >> ;
if(L <= mid) ans += query(L, R, lson);//L在mid左边
if(R > mid) ans += query(L, R, rson);//R在mid右边
return ans;
} int main(void){
int t, n;
scanf("%d", &t);
for(int i = ; i <= t; i++){
printf("Case %d:\n", i);
scanf("%d", &n);
build(, n, );
char s[];
while(scanf("%s", s) && s[] != 'E'){
int x, y;
scanf("%d%d", &x, &y);
if(s[] == 'Q') printf("%d\n", query(x, y, , n, ));
else if(s[] == 'A') updata(x, y, , n, );
else updata(x, -y, , n, );
}
}
return ;
}
最新文章
- 转:IOC框架
- Android核心机制
- memcached 基本操作
- Outlook 2013 在邮件里面点击超链接时弹出&ldquo;组织策略阻止我们为您完成此操作&rdquo;
- Tunnel Warfare
- intent和intentfilter
- Rabbitmq集群高可用
- 最短路径---dijkstra算法模板
- Machine Learning学习资源
- auth mysql
- MySQL 报错 1055
- 乾坤合一~Linux设备驱动之块设备驱动
- 关于Java实现的进制转化(位运算)
- 【Cmd】那些年,我们迷恋的cmd命令(一)
- 深入浅出 JMS(三) - ActiveMQ 消息传输
- Jquery 禁用元素的所有属性
- xpath的数据和节点类型以及XPath中节点匹配的基本方法
- jQuery插件开发之windowScroll
- list 返回列表null替换
- Socket初步了解
热门文章
- LeetCode:安排工作以达到最大收益【455】
- java编程实例
- C#SocketAsyncEventArgs实现高效能多并发TCPSocket通信 (服务器实现)
- skynet实践(9)-随机数重复问题
- C++ string的查找函数和npos特殊值
- ACM学习历程—SNNUOJ 1110 传输网络((并查集 &;&; 离线) || (线段树 &;&; 时间戳))(2015陕西省大学生程序设计竞赛D题)
- css 跳转电脑分辨率
- uC/OS-II源码分析(五)
- dataguard 常规运维操作
- bzoj 4671 异或图 —— 容斥+斯特林反演+线性基