116系类)
线段树和树状数组本身的组织都是二叉树的一种实现方式,从目前被我用到的地方来看,主要作用在于对于顺序的连续实体的资源和的查找十分迅速,线段树的表达能力比树状数组强很多,还能用在别的地方
结合题目来谈:
士兵杀敌(一)
KB
- 描述
-
南将军手下有N个士兵,分别编号1到N,这些士兵的杀敌数都是已知的。
小工是南将军手下的军师,南将军现在想知道第m号到第n号士兵的总杀敌数,请你帮助小工来回答南将军吧。
注意,南将军可能会问很多次问题。
-
- 输入
- 只有一组测试数据
第一行是两个整数N,M,其中N表示士兵的个数(1
随后的一行是N个整数,ai表示第i号士兵杀敌数目。(0<=ai<=100)
随后的M行每行有两个整数m,n,表示南将军想知道第m号到第n号士兵的总杀敌数(1<=m,n<=N)。 - 输出
- 对于每一个询问,输出总杀敌数
每个输出占一行 - 样例输入
-
5 2
-
1 2 3 4 5
-
1 3
-
2 4
- 样例输出
-
6 9
- 比如上述题目,如果采用一般的方法,直接用一个大小为N的列表去存士兵的杀敌数,每次命令之后都动态的去把m
-n 的数据区加一次,那么不用想这样的操作是肯定有问题的,最后的时间复杂度为
NM
1
2
3
1
1+2
1+2+3+4
5+6
1+2+3+4+5+6+7+8
-log2(m),也就是最后的时间复杂度为 2M*log2(N),空间复杂度并没有改变
java.util.Scanner;
//acm 108
public class SoldierKillEnemyV2 {
static void main(String[] args) {
SoldierKillEnemyV2 soldierKillEnemyV2 = new
SoldierKillEnemyV2();
soldierKillEnemyV2.solution();
solution() {
Scanner(System.in);
int[1000001];
getData();
System.out.println();
"";
0;
0;
0; i < times; i++) {
in.nextInt();
in.nextInt();
System.out.println(getSum(y) - getSum(x - 1));
in;
data;
soilders;
times;
getData() {
in.nextInt();
in.nextInt();
1; i <= soilders; i++) {
in.nextInt());
getMod2Max(int n) {
& (-n);
向Data中指定位置增加数字
addTodata(int n, int x) {
<= soilders) {
x;
getMod2Max(n);
返回前N项的和
getSum(int n) {
0;
> 0) {
data[n];