设题目数组arr
对于一个树状数组的修改和查询都是log(n)的速度, 树状数组都内置一个数组tr,
对于tr[i]的含义：以i为终点长度为lowbit(i)的arr的一个区间和也就是tr[i]为
S[i - lowbit(i) + 1, i]的值
举个例子对于我们需要查询的1~5的区间和
int res = tr[5] + x; => x = 5 - lowbit(5) = 4;
res = res + tr[4] + x; => x = 4 - lowbit(4) = 0
x == 0停止
因此1~5的前缀和就为tr[5] + tr[4];

下面介绍lowbit(i)
lowbit(i)可以简述为i的二进制表达中的最后一个1所代表的数值
如对于5而言101 ==> lowbit(5) = (1)2 = 1
  对于4而言100 ==> lowbit(4) = (100)2 = 4

给出代码实现
static int lowbit(int x) {
    return x & -x;
}

static void add(int x, int v) {
    for (int i = x; i <= n i += lowbit(i)) {
        tr[i] += v;
    }
}

static int query(int r) {
    int res = 0;
    for (int i = r; i > 0; i -= lowbit(i)) {
        res += tr[i];
    }
    return res;
}

单点修改区间查询(经典)

import java.util.*;

public class Main {
    static final int N = 100010;
    static int[] tr = new int[N];
    static int n, m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            add(i, sc.nextInt());
        }
        m = sc.nextInt();
        while (m -- > 0) {
            int ops = sc.nextInt();
            int a = sc.nextInt(), b = sc.nextInt();
            if (ops == 1) {
                add(a, b);
            } else {
                System.out.println(query(b) - query(a - 1));;
            }
        }
        sc.close();
    }

    static void add(int x, int v) {
        for (int i = x; i <= n; i += lowbit(i)) {
            tr[i] += v;
        }
    }

    static int query(int r) {
        int res = 0;
        for (int i = r; i > 0; i -= lowbit(i)) {
            res += tr[i];
        }
        return res;
    }

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

区间修改单点查询

题目

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

public class Main{
    static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(System.out);
    static final int N = 100010;
    static int[] a = new int[N], tr = new int[N];
    static int n, m;

    public static void main(String[] args) throws IOException {

        String[] s1 = sc.readLine().split(" ");
        n = Integer.parseInt(s1[0]); m = Integer.parseInt(s1[1]);

        String[] s2 = sc.readLine().split(" ");
        for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(s2[i - 1]);//读入原数组
        for (int i = 1; i <= n; i++) add(i, a[i] - a[i - 1]);//构建差分数组

        while (m -- > 0) {
            String[] str = sc.readLine().split(" ");
            if (str[0].equals("Q")) {//单点查询利用差分数组求前缀和得到单点数值
                int ans = sum(Integer.parseInt(str[1]));
                out.println(ans);
            } else {//区间修改, 利用差分数组单点修改高效区间修改：[l,r]加上c就是tr[l]+c, tr[r + 1]-c
                int l = Integer.parseInt(str[1]), r = Integer.parseInt(str[2]), c = Integer.parseInt(str[3]);
                add(l, c);
                add(r + 1, -c);
            }
        }

        out.flush();
    }

    static void add(int x, int c) {
        for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    }

    static int sum(int x) {
        int res = 0;
        for (int i = x; i > 0; i -= lowbit(i)) res += tr[i];
        return res;
    }

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