1264.动态求连续区间和Java题解（树状数组）

输入样例&＃xff1a;

10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8


输出样例&＃xff1a;

11
30
35

解题思路&＃xff1a;

树状数组&＃xff1a;&＃xff08;求动态数组的前缀和&＃xff09;

作用&＃xff1a;①给数组中某位置的数加一个数。②快速求前缀和。均为 O(logn)

本质&＃xff1a;单点查询&＃xff0c;区间修改

表示&＃xff1a;tree[x]&＃xff1a;表示 (x-lowbit(x), x] 之间的和。其中 lowbit(x):表示 2^k&＃xff0c;k为x在二进制形式下末尾0的个数。

 &＃xff08;树状数组的结构图&＃xff09;

操作&＃xff1a;①求前n项和。

②添加元素至数组。&＃xff08;对所有父节点元素均需要修改&＃xff09;

设当前结点索引为x&＃xff0c;则其父节点索引为 x&＃43;lowbit(x)。

Java代码&＃xff1a;

import java.io.*;public class Main{static int[]arr;static int[]tree;//树状数组public static void main(String[] args) throws IOException {BufferedReader br &＃61; new BufferedReader(new InputStreamReader(System.in));String[] split &＃61; br.readLine().split(" ");int n &＃61; Integer.parseInt(split[0]);int m &＃61; Integer.parseInt(split[1]);arr &＃61; new int[n &＃43; 1];tree &＃61; new int[n &＃43; 1];split &＃61; br.readLine().split(" ");for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;)arr[i] &＃61; Integer.parseInt(split[i - 1]);for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;) add(i, arr[i]);//初始化树状数组for(int i &＃61; 0; i 0; i -&＃61; lowbit(i)) res &＃43;&＃61; tree[i];return res;}public static void add(int x, int y) {//在索引为x的原数组上添加上yfor(int i &＃61; x; i }