HDU1166 敌兵布阵【线段树，Java数据结构和算法面试题及答案

72 阅读 0 评论 48 点赞

我是靠谱客的博主眼睛大寒风，最近开发中收集的这篇文章主要介绍HDU1166 敌兵布阵【线段树，Java数据结构和算法面试题及答案，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Sample Input

1 2 3 4 5 6 7 8 9 10

Query 1 3

Add 3 6

Query 2 7

Sub 10 2

Add 6 3

Query 3 10

End

Sample Output

Case 1:




### [](https://gitee.com/vip204888/java-p7)2.代码

单点更新

#define _CRT_SECURE_NO_WARNINGS

#include

using namespace std;

#define lson l,m,rt<<1 宏定义更方便

#define rson m + 1,r,rt<<1|1

const int maxn = 55555; //元素总个数

int sum[maxn << 2]; ///sum求和

void PushUP(int rt) ///更新父节点

{

sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];

}

void build(int l,int r,int rt) //建树

{

if (l == r)  ///到达叶节点

{

    scanf("%d", &sum[rt]);

	return ;

}

int m = (l + r) >> 1;

///左右递归

build(lson);

build(rson);

///更新信息

PushUP(rt);

}

///点修改

void update(int p, int add, int l, int r, int rt)//l,r表示当前节点区间，rt表示当前节点编号

{

if (l == r) //到叶节点，修改

{

	sum[rt] += add;

	return;

}

int m = (l + r) >> 1;

//根据条件判断往左子树调用还是往右 

if (p <= m) update(p, add, lson);

else update(p, add, rson);

PushUP(rt);//子节点更新了，所以本节点也需要更新信息

}

int query(int L, int R, int l, int r, int rt)//L,R表示操作区间，l,r表示当前节点区间，rt表示当前节点编号

{

if (L <= l && r <= R)

{

	return sum[rt];//在区间内，直接返回

}

int m = (l + r) >> 1;

//累计答案

int ans = 0;

if (L <= m) ans += query(L, R, lson);

if (R > m)  ans += query(L, R, rson);

return ans;

}

int main()