树状数组70分求调
查看原帖
树状数组70分求调
555950
wdgm4楼主2025/8/1 11:30

33 个点TLE。

import java.io.*;
import java.util.*;

public class Main {
  static int n, m;

  static class TreeArr {
    private long[] t = new long[500010];

    private int lowbit(int x) {
      return x & (-x);
    }

    public void add(int x, int y) {
      for (int i = x; i <= n; i += lowbit(i)) {
        t[i] += y;
      }
    }

    public long query(int x) {
      long ans = 0;
      for (int i = x; i > 0; i -= lowbit(i)) {
        ans += t[i];
      }
      return ans;
    }
  }

  public static void main(String args[]) {
    Scanner cin = new Scanner(System.in);
    n = cin.nextInt();
    m = cin.nextInt();

    TreeArr T = new TreeArr();
    for (int i = 1; i <= n; i++) {
      int mem = cin.nextInt();
      T.add(i, mem);
    }

    for (int i = 1; i <= m; i++) {
      int opt = cin.nextInt();
      if (opt == 1) {
        int x = cin.nextInt(), y = cin.nextInt();
        T.add(x, y);
      } else {
        int x = cin.nextInt(), y = cin.nextInt();
        long ans = T.query(y) - T.query(x - 1);
        System.out.println(ans);
      }
    }
  }
}

注:用 java 写的,不知道是因为 java 像 python 那样效率比较低就 T 了还是单纯代码有问题。QWQ

2025/8/1 11:30
加载中...