单点更新 区间查询
使用树状数组维护原数组即可
public class Test01 {
static final int N = 10010;
static int[] c = new int[N];
static int n;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
for (int i = 1; i <= n; i++) {
int x = in.nextInt();
update(i, x);
}
// 这里执行单点修改的代码
// q个查询,区间查询
int q = in.nextInt();
while (q-- > 0) {
int l, r;
l = in.nextInt();
r = in.nextInt();
System.out.println(sums(r) - sums(l - 1));
}
}
/**
* 更新原数组中的idx
*
* @param idx
* @param x
*/
public static void update(int idx, int x) {
while (idx <= n) {
c[idx] += x;
idx += idx & -idx;
}
}
/**
* 求原数组中a[1...j]的和
*
* @param j
* @return
*/
public static int sums(int j) {
int res = 0;
while (j > 0) {
res += c[j];
j -= j & -j;
}
return res;
}
}
区间更新 单点查询
使用树状数组维护原数组的差分数组
/**
* 树状数组
* 区间修改 单点查询
* 使用树状数组维护原数组的差分数组
*/
public class Test02 {
static final int N = 10010;
static int[] c = new int[N];
static int[] d = new int[N];
static int n;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
for (int i = 1; i <= n; i++) {
int x = in.nextInt();
update(i, x);
update(i + 1, -x);
}
// 这里执行区间修改的代码
// 单点查询,输出原数组
for(int i = 1; i <= n; i ++){
System.out.print(getsum(i) + " ");
}
}
/**
* 如果对区间a[l...r]+x 即 update(l, x);update(r + 1, -x);
* @param idx
* @param x
*/
public static void update(int idx, int x) {
while (idx <= n) {
c[idx] += x;
idx += idx & -idx;
}
}
/**
* 求原数组a[j]
* @param j
*/
public static int getsum(int j) {
int res = 0;
while(j > 0){
res += c[j];
j -= j & -j;
}
return res;
}
}