首页
登录 | 注册

java,线段树

线段树:

  你可以理解成:线段组成的树,很多人问我,线段树到底有何用处,其实这个问题,你可以自己去刷题,然后总结出检验。

线段的具体理解,我看到一篇很好的博客,我就不展开了。博客地址:https://blog.csdn.net/iwts_24/article/details/81484561

基础题目:

hdu1166 敌兵布阵

如果我们没有学过线段树,我们肯定是用模拟+暴力的方法。

模拟+暴力的方法代码:

package Combat.com;

import java.math.BigInteger;
import java.util.Scanner;

public class Main
{
    static final int MAX = 50005;
    static int camp[] = new int[MAX];
    public static void main(String []args)
    {
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        for(int i = 1; i <= T; i++)
        {
            int N = cin.nextInt();
            for(int j = 1; j <= N; j++)
            {
                camp[j] = cin.nextInt();
            }
            System.out.println("Case " + i +":" );
            search(N);
        }
    }
    static void search(int N)
    {
        Scanner cin = new Scanner(System.in);
        while(true)
        {
            String input = cin.next();
            if(input.equals("End"))
            {
                return;
            }
            int i = cin.nextInt();
            int j = cin.nextInt();
            if(input.equals("Add"))
            {
                camp[i] += j;
            }
            else if(input.equals("Sub"))
            {
                camp[i] -= j;
            }
            else
            {
                int output = 0;
                for(int k = i; k <= j; k++)
                {
                    output += camp[k];
                }
                System.out.println(output);
            }
        }
    }
}

上面的代码随着输入的用例越多,是极易超时的。

正确的方法是:线段树中的:单点修改+区间查询。

代码实现如下:

package Combat.com;

import java.util.Scanner;

public class Main
{
    static final int MAX = 50005;
    static int camp[] = new int[MAX*4];
    static Scanner cin = new Scanner(System.in);
    public static void main(String []args)
    {
        int T = cin.nextInt();
        for(int i = 1; i <= T; i++)
        {
            int N = cin.nextInt();
            buildBinaryTree(1,N,1);
            System.out.println("Case " + i + ":");
            search(N);
        }
    }
    static void search(int N)
    {
        while(true)
        {
            String input = cin.next();
            if(input.equals("End"))
            {
                return;
            }
            int i = cin.nextInt();
            int j = cin.nextInt();
            if(input.equals("Add"))
            {
                update(1,i,j,1,N);
            }
            else if(input.equals("Sub"))
            {
                update(1,i,-j,1,N);
            }
            else
            {
                System.out.println(query(1,i,j,1,N));
            }
        }
    }
    static int query(int node,int l,int r,int L,int R)//不用分开考虑是否跨区间。下面的代码已经考虑在内了。
    {
        if(l <= L && R <= r)
        {
            return camp[node];
        }
        int mid = (L+R)/2;
        int sum = 0;
        if(l <= mid)
        {
            sum += query(node*2,l,r,L,mid);
        }
        if(r > mid)
        {
            sum += query(node*2+1,l,r,mid+1,R);
        }
        return sum;
    }
    static void update(int node,int pos,int num,int L,int R)
    {
        if(L == R)
        {
            camp[node] += num;
            return;
        }
        int mid = (L+R)/2;
        if(pos <= mid)
        {
            update(node*2,pos,num,L,mid);
        }
        else
        {
            update(node*2+1,pos,num,mid+1,R);
        }
        camp[node] = camp[node*2]+camp[node*2+1];//这句话极其重要
    }
    static void buildBinaryTree(int L,int R,int node)
    {
        if(L == R)
        {
            camp[node] = cin.nextInt();
            return;
        }
        int mid = (L+R)/2;
        buildBinaryTree(L,mid,node*2);
        buildBinaryTree(mid+1,R,node*2+1);
        camp[node] = camp[node*2]+camp[node*2+1];
    }
}

 HDU1754: 

也是一道单点修改+区间查询。,我出错:主要是数组开得太大了,显示:Memory Limit Exceeded。即是超内存

代码实现实现如下:

import java.util.Scanner;

public class Main
{
    static final int MAX = 200005;
    static int result[] = new int[MAX*4];
    static Scanner cin = new Scanner(System.in);
    public static void main(String []args)
    {
        while(cin.hasNext())
        {
            int N = cin.nextInt();
            int M = cin.nextInt();
            buildBinaryTree(1,N,1);
            search(N,M);
        }
    }
    static void search(int N,int M)
    {
        for(int i = 1; i <= M; i++)
        {
            String input = cin.next();
            int a = cin.nextInt();
            int b = cin.nextInt();
            if(input.equals("U"))
            {
                update(a,b,1,N,1);
            }
            else
            {
                System.out.println(query(a,b,1,N,1));
            }
        }
    }
    static int query(int l,int r,int L,int R,int node)
    {
        if(l <= L && R <= r)
        {
            return result[node];
        }
        int mid = (L+R)/2;
        int Max = 0;
        if(l <= mid)
        {
            Max = Math.max(Max,query(l,r,L,mid,node*2));
        }
        if(mid < r)
        {
            Max = Math.max(Max,query(l,r,mid+1,R,node*2+1));
        }
        return Max;
    }
    static void update(int pos,int num,int L,int R,int node)
    {
        if(L == R)
        {
            result[node] = num;
            return;
        }
        int mid = (L+R)/2;
        if(pos <= mid)
        {
            update(pos,num,L,mid,node*2);
        }
        else
        {
            update(pos,num,mid+1,R,node*2+1);
        }
        result[node] = Math.max(result[node*2], result[node*2+1]);
    }
    static void buildBinaryTree(int L,int R,int node)
    {
        if(L == R)
        {
            result[node] = cin.nextInt();
            return;
        }
        int mid = (L+R)/2;
        buildBinaryTree(L,mid,node*2);
        buildBinaryTree(mid+1,R,node*2+1);
        result[node] = Math.max(result[node*2], result[node*2+1]);
    }
}

 

 

 

  1.  
     

相关文章

  • 一.前言 在日常开发中,我们经常会碰到需要在运行时才知道对象个数的情况,这种情况不能使用数组,因为数组是固定数量的,这个时候我们就会使用集合,因为集合可以存储数量不确定的对象. 集合类是特别有用的工具类,不仅可以存储数量不等的对象,还可以实 ...
  • 为什么说 Java 程序员到了必须掌握 Spring Boot 的时候?
    Spring Boot 2.0 的推出又激起了一阵学习 Spring Boot 热,就单从我个人的博客的访问量大幅增加就可以感受到大家对学习 Spring Boot 的热情,那么在这么多人热衷于学习 Spring Boot 之时,我自己也在 ...
  • final关键字可用于修饰类.方法和变量,final修饰的类不能被继承:final修饰的方法不可被重写:final修饰的变量不可被改变. 1. final类 final修饰的类不能被继承意思是final修饰的类不可以有子类,java.lan ...
  • java中常见的集合类大部分是非线程安全的,在多线程情况下会报并发修改异常(ConcurrentModificationException) 并发下的ArrayList类: 1 //集合类不安全的例子 2 public class Coll ...
  • java游戏开发杂谈
    线程,让游戏拥有了动态变化的能力. java的图形界面,在启动的时候,就开始了一个线程. 这个线程负责处理:JFrame.JPanel等的绘制.事件处理. 它是由操作系统调用的,在程序启动时开启,程序关闭时消亡. 这个线程里执行的逻辑,支撑 ...
  • 最近老师老是不讲新课,好繁!!! 还是来说抽象类吧. public abstract class A{ //因为下边有一个抽象方法,所以这就必须要是一个抽象类,要不然编译不能通过 public void c(){ System.out.pr ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.078 s.
京ICP备10005923号