现在的位置: 首页 > 综合 > 正文

树状数组与线段树入门

2019年06月12日 ⁄ 综合 ⁄ 共 2049字 ⁄ 字号 评论关闭
最近开始接触到了线段树和树状数组的题目 (refer to acm
116系类)
线段树和树状数组本身的组织都是二叉树的一种实现方式,从目前被我用到的地方来看,主要作用在于对于顺序的连续实体的资源和的查找十分迅速,线段树的表达能力比树状数组强很多,还能用在别的地方

结合题目来谈:

士兵杀敌(一)

时间限制:1000 ms
  内存限制:65535
KB
难度:3
描述

南将军手下有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
的数据区加一次,那么不用想这样的操作是肯定有问题的,最后的时间复杂度为
NM

         这样肯定不能满足性能需求,那么现在怎么办呢,此时树状数组和线段树的作用就体现出来了,

        树状数组的解决方案是修改原始数据的存储方式

        树状数组使用长度仍为N的数组去记录数据,但是数据点的含义发生了变化,树状数组的原始数据满足一下规律:

       奇数节点记录着原始数据,

       偶数节点记录着包含本身在内的前n个数据的和(n满足n为能被该偶数的最大的2的倍数)

      e.g.

     
     
    
3      
  4    
    5
   6
   7  
     
     
   8

     
   
1+2  
1+2+3+4  
5+6  
1+2+3+4+5+6+7+8

     上面举出了长度为8的树状数组的数据结构,第一个存第一个数据的值,第二节点存 第一和第二的数据和

     这样的结构带来了怎么样的影响,我们就可以发现现在查询一条记录的时间被积聚所见了,如查询m-n的数据和,那么这样的时间复杂度为 log2(n)
-log2(m),也就是最后的时间复杂度为 2M*log2(N),空间复杂度并没有改变

    实现的代码

    import
java.util.Scanner;

//acm 108   树状数组版
public class SoldierKillEnemyV2 {
    public
static void main(String[] args) {
   
   
SoldierKillEnemyV2 soldierKillEnemyV2 = new
SoldierKillEnemyV2();
   
   
soldierKillEnemyV2.solution();
    }

    public void
solution() {
   
    in = new
Scanner(System.in);
   
    data = new
int[1000001];
   
   
getData();
   
   
System.out.println();
   
    String cmd =
"";
   
    int x =
0;
   
    int y =
0;
   
    for (int i =
0; i < times; i++) {
   
   
    x =
in.nextInt();
   
   
    y =
in.nextInt();
   
   
   
System.out.println(getSum(y) - getSum(x - 1));
   
    }
    }

    Scanner
in;
    int[]
data;
    int
soilders;
    int
times;

    private void
getData() {
   
    soilders =
in.nextInt();
   
    times =
in.nextInt();
   
    for (int i =
1; i <= soilders; i++) {
   
   
    addTodata(i,
in.nextInt());
   
    }
    }

    private int
getMod2Max(int n) {
   
    return n
& (-n);
    }

    //
向Data中指定位置增加数字
    private void
addTodata(int n, int x) {
   
    while (n
<= soilders) {
   
   
    data[n] +=
x;
   
   
    n +=
getMod2Max(n);
   
    }
    }

    //
返回前N项的和
    private int
getSum(int n) {
   
    int result =
0;
   
    while (n
> 0) {
   
   
    result +=
data[n];
   
   
 

【上篇】
【下篇】

抱歉!评论已关闭.