问题描述

操作格子蓝桥杯java线段树也超限怎么办

如题：
问题描述
有n个格子，从左到右放成一排，编号为1-n。

共有m次操作，有3种操作类型：

1.修改一个格子的权值，

2.求连续一段格子权值和，

3.求连续一段格子的最大值。

对于每个2、3操作输出你所求出的结果。

输入格式
第一行2个整数n，m。

接下来一行n个整数表示n个格子的初始权值。

接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间[x,y]内格子权值和，p=3时表示求区间[x,y]内格子最大的权值。

输出格式
有若干行，行数等于p=2或3的操作总数。

每行1个整数，对应了每个p=2或3操作的结果。

样例输入
4 3
1 2 3 4
2 1 3
1 4 3
3 1 4
样例输出
6
3
数据规模与约定
对于20%的数据n <= 100，m <= 200。

对于50%的数据n <= 5000，m <= 5000。

对于100%的数据1 <= n <= 100000，m <= 100000，0 <= 格子权值 <= 10000。

我用的java，用线段树写的，结果还是时间超限，高手求解
代码如下：

/**

• 线段树，操作格子
• @author Administrator
  *
  */
  class Node
  {
  int max,sum;
  int left,right;
  Node lNode,rNode;
  //构造方法
  Node()
  {
  max = 0;
  sum = 0;
  lNode = null;
  rNode = null;
  }

}
public class Tree {
//创建树
public static Node createTree(int left,int right)
{
Node xNode = new Node();

    xNode.left  = left;
    xNode.right = right;

    if(left != right)
    {
        int mid     = (left + right) / 2;

        xNode.lNode = createTree(left,mid);         //创建左子树
        xNode.rNode = createTree(mid+1,right);      //创建右子树

    }
    return xNode;
}

//为线段树赋权值
public static void insert(Node xNode,int point, int value)
{
    xNode.sum += value;
    xNode.max = value > xNode.max ? value:xNode.max;//修改经过的节点的值   

    if(xNode.left == xNode.right)                   //找到最终节点结束
        return;
    else
    {
        int mid  = (xNode.left + xNode.right) / 2;

        if(point <= mid)
            insert(xNode.lNode,point,value);        //向左修改
        else
            insert(xNode.rNode,point,value);        //向右修改
    }
    return;
}

//操作1：修改格子权值
public static void revise(Node xNode,int point,int value)
{
    if(xNode.left == point && xNode.right == point)
    {
        xNode.max = value;
        xNode.sum = value;
        return;
    }
    else
    {
        int mid = (xNode.left + xNode.right) / 2;

        if(point <= mid)
            revise(xNode.lNode,point,value);            //递归入，寻找节点
        else
            revise(xNode.rNode,point,value);

        xNode.sum = xNode.lNode.sum + xNode.rNode.sum;  //递归出，从下往上修改和
        xNode.max = xNode.lNode.max > xNode.rNode.max ?
                    xNode.lNode.max : xNode.rNode.max;
    }
}
//操作2：求连续一段格子的权值和
public static int getSum(Node xNode,int left,int right)
{
    if(xNode.left == left && xNode.right == right)  //找到节点
        return xNode.sum;
    else
    {
        int mid  = (xNode.left + xNode.right) / 2;

        if(right <= mid)                            //向左子树搜索
            return getSum(xNode.lNode,left,right);
        else
            if(left > mid)                          //向右子树搜索
                return getSum(xNode.rNode,left,right);
            else                                    //左右子树分叉搜索，求和
                return getSum(xNode.lNode,left,mid) + getSum(xNode.rNode,mid+1,right);
    }
}
//操作3：求连续一段格子的最大值
public static int getMax(Node xNode,int left,int right)
{
    if(xNode.left == left && xNode.right == right)  //找到当前节点
        return xNode.max;
    else
    {
        int mid = (xNode.left + xNode.right) / 2;

        if(right <= mid)                            //搜索左子树
            return getMax(xNode.lNode,left,right);
        else
            if(left > mid)                          //搜索右子树
                return getMax(xNode.rNode,left,right);
            else                                    //左右子树分叉搜索，取最大值
                return getMax(xNode.lNode,left,mid) > getMax(xNode.rNode,mid + 1,right) ?
                       getMax(xNode.lNode,left,mid) : getMax(xNode.rNode,mid + 1,right);
    }
}
public static void main(String[] args)
{

    int m = 0,n = 0;
    Node xNode = null;

    java.util.Scanner cin = new java.util.Scanner(System.in);

    n = cin.nextInt();
    m = cin.nextInt();

    xNode = createTree(1,n);

    for(int i = 1;i<=n;i++)
    {
        int value = cin.nextInt();
        insert(xNode,i,value);
    }

    while(m>0)
    {
        m--;
        int p,x,y;

        p = cin.nextInt();
        x = cin.nextInt();
        y = cin.nextInt();
        switch(p)
        {
        case 1 : revise(xNode,x,y); break;
        case 2 : System.out.println(getSum(xNode,x,y)); break;
        case 3 : System.out.println(getMax(xNode,x,y)); break;
        default:                                        break;
        }
    }
    cin.close();
    return;

}

}

解决方案

 package main;
import java.util.Scanner;
public class Main {
 private Integer[] shuzu;
 public static void main(String[] args) {
  Scanner scan = new Scanner(System.in);
  String str = scan.nextLine();
  String[] str1 = str.split(" ");
  String caozuo = str1[1];
  Main main = new Main(str1[0]);
  String initNum = scan.nextLine();
  main.init(initNum);
  for (int i = 0; i < Integer.valueOf(caozuo); i++) {
   String operator = scan.nextLine();
   String[] operators = operator.split(" ");
   int num1 = Integer.valueOf(operators[1]);
   int num2 = Integer.valueOf(operators[2]);
   switch (operators[0]) {
   case "1":
    main.service1(num1,num2);
    break;
   case "2":
    main.service2(num1,num2);
    break;
   case "3":
    main.service3(num1,num2);
   }
  }
 }
 public Main(String x) {
  Integer i = Integer.valueOf(x);
  this.shuzu = new Integer[i];
 }
 public void init(String str) {
  String[] strNums = str.split(" ");
  for (int i = 0; i < strNums.length; i++) {
   this.shuzu[i] = Integer.valueOf(strNums[i]);
  }
 }
 private void service1(int x, int y) {
  this.shuzu[--x] = y;
 }
 private void service2(int x, int y) {
  int total=0;
  for(;x<=y;x++){
   total += this.shuzu[x-1];
  }
  System.out.println(total);
 }
 private void service3(int x, int y) {
  int maxNum =0;
  for(;x<=y;x++){
   if(maxNum<this.shuzu[x-1])
   {
    maxNum=this.shuzu[x-1];
   }
  }
  System.out.println(maxNum);
 }
}