# 1、遍历法

package RangeSum;

public class Traversal {

public static int traversal(int[] arr,int start,int end){
int res = 0;
if(start < 0 || start >arr.length || end > arr.length){
System.out.println("index error");
return -999;
}
for(int i=start;i<=end;i++){
res += arr[i];
}
return res;
}

public static void main(String[] args){
int[] arr = {5,3,2,8,7,10,13,6};
//2 + 8 + 7 + 10 + 13 = 40
System.out.println(traversal(arr,2,6));
}
}

# 2、辅助数组法

package RangeSum;

public class AuxiliaryArr {

public static int[] auxiliary(int[] arr){
if(arr == null || arr.length <= 0)
return null;
int[] aux = new int[arr.length];
aux[0] = arr[0];
for(int i=1;i<arr.length;i++){
aux[i] = aux[i-1] + arr[i];
}
return aux;
}

public static int sumRange(int[] arr,int start,int end){
if(start < 0 || start >arr.length || end > arr.length){
System.out.println("index error");
return -999;
}
else if(start == 0){
return arr[end];
}
else{
return arr[end] - arr[start-1];
}

}

public static void main(String[] args){
int[] arr = {5,3,2,8,7,10,13,6};
//2 + 8 + 7 + 10 + 13 = 40
int[] auxiliaryArr = auxiliary(arr);
System.out.println(sumRange(auxiliaryArr,2,6));
}
}

# 3、树状数组法

C[1]=A[1];
C[2]=A[1]+A[2];
C[3]=A[3];
C[4]=A[1]+A[2]+A[3]+A[4];
C[5]=A[5];
C[6]=A[5]+A[6];
C[7]=A[7];
C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];

1=(001)      C[1]=A[1];
2=(010)      C[2]=A[1]+A[2];
3=(011)      C[3]=A[3];
4=(100)      C[4]=A[1]+A[2]+A[3]+A[4];
5=(101)      C[5]=A[5];
6=(110)      C[6]=A[5]+A[6];
7=(111)      C[7]=A[7];
8=(1000)    C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];

C[m]=A[m-2^k+1]+A[to-2^k+2]+......A[m];

sumRange[from:to] = A[from] + A[from + 1] +..+A[to] = sum[from:to - 2^k] + C[to]

C[to] = A[to-2^k+1]+A[to-2^k+2]+......A[to];

public static int lowbit(int t){        return t & (-t);}

int[] arr = null;
int[] bitArr = null;
int n = 0;

public BIT(int[] arr){
this.arr = new int[arr.length + 1];
for(int i=0;i<arr.length;i++){
this.arr[i+1] = arr[i];
}
this.n = arr.length;
this.initBitArr();
}

public void initBitArr(){
bitArr = new int[this.arr.length];
for(int i=1;i<=this.arr.length;i++){
this.update(i);
}
}

public void update(int index){
for(int i=index;i <=n ;i += lowbit(i)){
this.bitArr[i] += this.arr[index];
}
}

public int sum(int from1,int to1){
int ans1 = 0;
int ans2 = 0;
int from = from1 + 1;
int to = to1 + 1;
for(int i=to;i>0;i-= lowbit(i)){
ans1 += this.bitArr[i];
}
if(from1 > 0){
for(int i=from-1;i>0;i-= lowbit(i)){
ans2 += this.bitArr[i];
}
}
return ans1-ans2;
}

package RangeSum;

public class BIT {

int[] arr = null;
int[] bitArr = null;
int n = 0;

public BIT(int[] arr){
this.arr = new int[arr.length + 1];
for(int i=0;i<arr.length;i++){
this.arr[i+1] = arr[i];
}
this.n = arr.length;
this.initBitArr();
}

public void initBitArr(){
bitArr = new int[this.arr.length];
for(int i=1;i<=this.arr.length;i++){
this.update(i);
}
}

public void update(int index){
for(int i=index;i <=n ;i += lowbit(i)){
this.bitArr[i] += this.arr[index];
}
}

public int sum(int from1,int to1){
int ans1 = 0;
int ans2 = 0;
int from = from1 + 1;
int to = to1 + 1;
for(int i=to;i>0;i-= lowbit(i)){
ans1 += this.bitArr[i];
}
if(from1 > 0){
for(int i=from-1;i>0;i-= lowbit(i)){
ans2 += this.bitArr[i];
}
}
return ans1-ans2;
}

public static int lowbit(int t){
return t & (-t);
}

public static void main(String[] args){
int[] arr = {1,2,3,4,5,6,7,8};
//System.out.println(traversal(arr,2,6));
BIT bit = new BIT(arr);
System.out.println(bit.sum(0,6));

}
}

0 条评论

• ### 各种排序算法的分析及java&python实现

排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。下面讲的排序都是属于内排序。...

• ### 盘一盘 NumPy (上)

Numpy 是 Python 专门处理高维数组 (high dimensional array) 的计算的包，每次使用它遇到问题都会它的官网 (www.num...

• ### 一招解决4道leetcode hard题，动态规划在字符串匹配问题中的应用

在做leetcode的时候，遇到hard题大家往往都觉得头疼，但其实，掌握方法，举一反三，hard题有时候我们也能想到好的思路，顺利攻破，今天我们就介绍一下动态...

• ### java基础学习_基础语法(下)01_day05总结

============================================================================= ==...

• ### Java 语法（五）：数组

当然，一般情况下我们更喜欢使用第一种方式来声明一个数组，因为它将类型与变量名分开，优化了代码的可读性。刚刚我们只是声明了一个数组 a ，但是并没有将 a 初始化...

• ### 【Java】04 数组

初始化：   静态初始化：初始化时由程序员显式指定每个数组元素的初始值，由系统决定数组长度。   动态初始化：初始化时程序员只指定数组长度，由系统为数组元素...

• ### LeetCode刷题记录：剑指 Offer 10- I. 斐波那契数列

解题思路： 根据输入的 n 声明一个数组，定义好数组的前两个元素（即第 0 项和第 1 项），从第三个元素开始遍历数组，使数组的每一个元素等于前两个元素之和。...

• ### [算法题] 荷兰国旗问题

假设这样的条纹有多条，且各种颜色的数量不一，并且随机组成了一个新的图形，新的图形可能如下图所示，但是绝非只有这一种情况：

• ### 如何实现归并排序？

划分步骤很简单：将当前数组分成两半（如果N是偶数，则将其完全平等，或者如果N是奇数，则一边稍大于一个元素），然后递归地对这两半进行排序。