HDOJ 1166敌兵布阵 线段树应用 提交超时
HDOJ1166敌兵布阵 http://acm.hdu.edu.cn/showproblem.php?pid=1166
是简单的线段树的应用，结果是对的，可以提交总是超时，哪位大侠能帮我看下问题在哪里吗？
多谢。
代码：
//HDOJ 1166 敌兵布阵（http://acm.hdu.edu.cn/showproblem.php?pid=1166）
//线段树的应用
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
const int MA_LEN = 50010;
//线段树需要4倍的存储空间
int sum[MA_LEN << 2];
//函数：构建线段树
void construct(int index,int left,int right);
//函数：更新线段树，增加营地人数
void add(int index,int left,int right,int flag,int num);
//函数：更新线段树，减少营地人数
void sub(int index,int left,int right,int flag,int num);
//函数：查询线段树
int query(int index,int left,int right,int l,int r);
int main(){
int T;
int count = 0;
cin >> T;
while(T--){
++count;
int N;
cin >> N;
construct(1,1,N);
string str;
int l,r;
cout << "Case " << count << ":" << endl;
while(1){
//getchar();
cin >> str;
if (str == "End")
break;
cin >> l >> r;
if (str == "Add")
{
add(1,1,N,l,r);
}
else if (str == "Sub")
{
sub(1,1,N,l,r);
}
else if(str == "Query"){
cout << query(1,1,N,l,r) << endl;
}
}
}
return 0;
}
//函数：构建线段树
//参数：
//index：当前线段树节点的索引
//left、right：当前线段树节点表示的区间
void construct(int index,int left,int right){
int val;
if (left == right)
{
cin >> val;
sum[index] = val;
}
else{
int mid = (left + right) >> 1;
//递归构建左孩子
construct(index << 1,left,mid);
//递归构建右孩子
construct((index << 1) + 1,mid + 1,right);
//根节点中存储的是总的数目，因此是左孩子节点值与右孩子节点值之和
sum[index] = sum[index << 1] + sum[(index << 1) + 1];
}
}
//函数：更新线段树
//参数：
//index:当前线段树节点索引
//left,right当前线段树节点表示的区间
//flag：要修改的区间中的某一点
//num：要改成的目标值
void add(int index,int left,int right,int flag,int num){
if (left == right)
{
sum[index] += num;
}
else{
int mid = (left + right) >> 1;
if (flag <= mid)
{
add(index << 1,left,mid,flag,num);
}
else
add((index << 1) + 1,mid + 1,right,flag,num);
sum[index] = sum[index << 1] + sum[(index << 1) + 1];
}
}
//函数：更新线段树
//参数：
//index:当前线段树节点索引
//left,right当前线段树节点表示的区间
//flag：要修改的区间中的某一点
//num：要改成的目标值
void sub(int index,int left,int right,int flag,int num){
if (left == right)
{
sum[index] -= num;
}
else{
int mid = (left + right) >> 1;
if (flag <= mid)
{
sub(index << 1,left,mid,flag,num);
}
else
sub((index << 1) + 1,mid + 1,right,flag,num);
sum[index] = sum[index << 1] + sum[(index << 1) + 1];
}
}
//函数：查询线段树
//参数：
//index：当前线段树节点索引
//left、right：当前线段树节点表示的区间
//l、r：要查询的区间
int query(int index,int left,int right,int l,int r){
if (left == l && right == r)
{
return sum[index];
}
else{
int mid = (left + right) >> 1;
//在左子树中递归查找
if (r <= mid)
{
query(index << 1,left,mid,l,r);
}
//在右子树中递归查找
else if (l > mid)
{
query((index << 1) + 1,mid + 1,right,l,r);
}
//分成两部分
else{
int a = query(index << 1,left,mid,l,mid);
int b = query((index << 1) + 1,mid + 1,right,mid + 1,r);
return a + b;
}
}
}
}
//在右子树中递归查找
else if (l > mid)
{
query((index << 1) + 1,mid + 1,right,l,r);
}
都不return你想干啥………………
