数状数组的学习与分析

文章目录

• 树状数组是什么
• 树状数组完整原理推导
• • 一.树状数组核心思想
  • 二.前缀和查询原理
  • 三.单点更新原理
  • • 重点注释：
  • 四.多语言代码展示
  • • 引用牛客PEEK73 【模板】动态区间和Ⅰ ‖ 单点修改 + 区间查询
    • Java的代码如下：
    • C++代码如下：
    • C语言代码如下：
    • Python代码如下：
    • 树状数组代码时间+空间复杂度汇总表
• 树状数组的更多应用：
• • 1.区间增量与单点求值
  • • 引用：牛客PEEK74 区间增量与单点求值
  • 2.区间增值和区间求和
  • • 引用洛谷P3372 【模板】线段树 1
    • • 解法一.树状数组暴力解法
      • 解法二.双树状数组模拟解法
      • 一、基础定义
      • 二、步骤1：证明差分数组前缀和 $c[k]=a_k$
      • 三、步骤2：推导原数组前 $k$
      • • 交换二重求和顺序
        • 拆分求和项
      • 四、最终结论
      • 解法三.线段树经典解法
  • 3.二进制区间取反与单点求值
  • • 引用：牛客PEEK75 区间取反与单点求值
    • • 思考
  • 4.二维单点增加和范围查询
  • 5.二维范围增加和范围查询
  • • 引用洛谷P4514
    • • 二维区间加、区间求和完整数学推导
      • • 1. 基础定义
        • 2. 定义全局前缀和 $S(x,y)$
        • 3. 交换求和顺序
        • 4. 展开多项式 $(x-p+1)(y-q+1)$
        • 5. 代入拆分四项求和
        • 6. 定义四个二维前缀和（对应代码4棵树）
• 总结一下

树状数组是什么

试想一下：在上世纪在上世纪 90 年代，无损压缩领域广泛使用算术编码（一种可以逼近理论压缩极限的无损压缩算法，核心原理是将一整段文本映射到区间[0,1)内唯一小数完成压缩，编码、解码全程需要频繁查询符号累积出现总次数，也就是累积频率表，因此要解决自适应算术编码中累积频率表动态维护的问题），所以这个时候前缀和，暴力遍历求解，平衡二叉树就挑起了担子，我们知道前缀和在求加和的时候需要O(n) 的时间复杂度（即求l,r的下标数组和需要构建前缀和数组，然后前缀和数组的第r项减去第l-1项即可），而暴力求解即为O(n),在多次查询加和的时候就会更耗时间，而虽然平衡二叉树可以做 O(logn) 的时间复杂度，但逻辑复杂，代码量大，且依赖指针节点内存开销大、内存访问不连续缓存效率差，实际运行常数就会很高，所以这个时候还是会想到计算机底层的0和1，如果我能把数字插为2的幂（即以二进制的形式）用于计算加和，且利用 lowbit 拆分下标分段存储局部区间和的思想，树状数组就诞生了。

树状数组完整原理推导

我们用一段推导来表达它的原理：

一.树状数组核心思想

我们在这里对任意数组下标

x

x

x，

t

r

e

e

[

x

]

tree[x]

tree[x]专门维护一段连续区间： 区间右端点固定为

x

x

x，区间长度等于

l

o

w

b

i

t

(

x

)

lowbit(x)

lowbit(x)，这样的区域为下标x所管辖的区域。 假设有一个下标1~16的数组，我们每次通过对半开的形式，然后计算各下标单独管辖范围：

• $x=1$
• $x=2$
• $x=3$
• $x=4$
• $x=5$
• $x=6$
• $x=7$
• $x=8$
• $x=9$
• $x=10$
• $x=11$
• $x=12$
• $x=13$
• $x=14$
• $x=15$
• $x=16$

二.前缀和查询原理

求前缀和

s

u

m

(

1

∼

x

)

sum(1\\sim x)

sum(1∼x)流程：

三.单点更新原理

给下标

x

x

x数值增加

v

v

v流程：

原理：所有右端点大于

x

x

x、且管辖区间包含下标

x

x

x的树状数组节点，都需要同步更新数值。 这里也是一样，对一个值进行更行，比如给第3个元素加一个v，我们要看它的树状数组每个下标，看有哪几个管辖这下标3，它们的值都要加上一个v，那应该怎么做呢？其实还是位运算，3的二进制是0011，那我们减去最右边的1，然后再加上原二进制加上它最右侧的1，就是0010+0010=0100（就是4的二进制），和上面的推导相符，然后接着这样（直到越界）就可找到每一个管辖了3的下标，把它们都加上一个v，这样我们就修改成功了。

重点注释：

树状数组的核心是要取一个数字二进制的最右边的1，那为啥x&(-x)能实现呢，推导过程如下：

11的二进制是00001011，对它进形结论中的操作：
+11原码：00001011
-11原码：10001011
-11反码：11110100
-11补码：11110101
0 0 0 0 1 0 1 1
1 1 1 1 0 1 0 1
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
0 0 0 0 0 0 0 1
可知11的二进制最低位的1恰好是原数最低位的1
其实就是负数用补码（按位取反 + 1），使x与-x仅在最低位 1 处同为 1，按位与便只取出该位权值，得到它二进制最低位1的位置
即证明

四.多语言代码展示

基于以上原理：

引用牛客PEEK73 【模板】动态区间和Ⅰ ‖ 单点修改 + 区间查询

题目链接如下： 牛客树状数组模版题 同样的牛客这个题对应洛谷的P3374,链接如下： 洛谷P3374树状数组模版题

Java的代码如下：

import java.io.*;
import java.util.*;
public class Main{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out=new PrintWriter(System.out);
static StringTokenizer st;
static int N=500010;//按题目开出一个合适的空间
static long []Tree;
static int op;
static int n;
static int m;
public static int lowbit(int x){//核心方法：取出二进制最右边的1
return x&(–x);
}
public static void add(int x,int v){
while(x<=N){//和上面的推导一样
Tree[x]+=v;//把这些管辖了x的下标元素都加v
x+=lowbit(x);//找到每位管辖x的下标
}
}
public static long query(int x){
long res=0;
while(x>0){
res+=Tree[x];//再把每个下标的元素相加
x-=lowbit(x);//我们不断抹去x的二进制最右边的1
}
return res;
}
public static void main(String[] args) throws IOException{
Tree = new long[N + 1];
st=new StringTokenizer(br.readLine());
n=Integer.parseInt(st.nextToken());
m=Integer.parseInt(st.nextToken());
st=new StringTokenizer(br.readLine());
for(int i=1;i<=n;i++){
int num=Integer.parseInt(st.nextToken());
add(i,num);//这个一定不要忘记了，就是要初始化
}
while(m—>0){
st=new StringTokenizer(br.readLine());
op=Integer.parseInt(st.nextToken());
if(op==1){
int i=Integer.parseInt(st.nextToken());
int x=Integer.parseInt(st.nextToken());
add(i,x);
}else{
int l=Integer.parseInt(st.nextToken());
int r=Integer.parseInt(st.nextToken());
out.println(query(r)–query(l–1));
}
}
out.flush();
br.close();
out.close();
}
}

C++代码如下：

//思路和前面的一样
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 10000010;
static ll Tree[N];
static ll n, m,op;
static ll lowbit(ll x) {
return x & (–x);
}
static void add(ll x, ll v) {
while (x <= N) {
Tree[x] += v;
x += lowbit(x);
}
}
static ll query(ll x) {
ll res = 0;
while (x > 0) {
res += Tree[x];
x -= lowbit(x);
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int num;
cin >> num;
add(i, num);
}
while (m—) {
cin>>op;
if(op==1){
int i,x;
cin>>i>>x;
add(i,x);
}else{
int l,r;
cin>>l>>r;
cout<<query(r)–query(l–1)<<"\\n";
}
}
return 0;
}

C语言代码如下：

//和前面的思路也一样
#include <stdio.h>
typedef long long ll;
const int N = 500010;
ll Tree[N];
static int lowbit(int x) {
return x & (–x);
}
static void add(int x, ll v) {
while (x <= N) {
Tree[x] += v;
x += lowbit(x);
}
}
static ll query(int x) {
ll res = 0;
while (x > 0) {
res += Tree[x];
x -= lowbit(x);
}
return res;
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
ll num;
scanf("%lld", &num);
add(i, num);
}
while (m—) {
int op;
scanf("%d", &op);
if (op == 1) {
int i;
ll x;
scanf("%d %lld", &i, &x);
add(i, x);
} else {
int l, r;
scanf("%d %d", &l, &r);
printf("%lld\\n", query(r) – query(l – 1));
}
}
return 0;
}

Python代码如下：

# 和前面的思路也相同
import sys
def main():
data = list(map(int, sys.stdin.read().split()))
ptr = 0
N = 500010
Tree = [0] * (N + 1)
def lowbit(x):
return x & –x
def add(x, v):
while x <= N:
Tree[x] += v
x += lowbit(x)
def query(x):
res = 0
while x > 0:
res += Tree[x]
x -= lowbit(x)
return res
n = data[ptr]
ptr += 1
m = data[ptr]
ptr += 1
for i in range(1, n + 1):
num = data[ptr]
ptr += 1
add(i, num)

output = []
for _ in range(m):
op = data[ptr]
ptr += 1
if op == 1:
i = data[ptr]
ptr += 1
val = data[ptr]
ptr += 1
add(i, val)
else:
l = data[ptr]
ptr += 1
r = data[ptr]
ptr += 1
res = query(r) – query(l – 1)
output.append(str(res))

print('\\n'.join(output))

if __name__ == "__main__":
main()

它的时间复杂度如下：

树状数组代码时间+空间复杂度汇总表

树状数组的更多应用：

1.区间增量与单点求值

引用：牛客PEEK74 区间增量与单点求值

题目链接如下： 牛客PEEK74区间增量与单点求值 同样的牛客这道题对应洛谷P3368,题目链接如下： 洛谷P3368区间增量与单点求值 其实在这里这个题唯一的改变就是从只改单个值，变为了区间改值，那我们在区间改值下能想到啥？就是差分，差分顾名思义，就是数组的前后两项相减，即：b[i]=a[i]-a[i-1],经典的模版如下：

//实现一维差分
import java.io.*;
import java.util.*;
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(System.out);
static StringTokenizer st;
static int n,m;
public static void main(String[] args) throws IOException{
st=new StringTokenizer(br.readLine());
n=Integer.parseInt(st.nextToken());
m=Integer.parseInt(st.nextToken());
int[] a=new int[n+1];
st=new StringTokenizer(br.readLine());
for(int i=1;i<=n;i++){
a[i]=Integer.parseInt(st.nextToken());
}
int []b=new int[n+2];
b[1]=a[1];//差分数组的第一项就是原数组的第一项
for(int i=2;i<=n;i++){
b[i]=a[i]–a[i–1];//构建一个差分数组
}
while(m— > 0){
st=new StringTokenizer(br.readLine());
int l=Integer.parseInt(st.nextToken());
int r=Integer.parseInt(st.nextToken());
int k=Integer.parseInt(st.nextToken());
//对于修改l~r范围的值都加个k,为啥可以这样呢?
//原理：差分数组求前缀和还原原数组
//1.b[l]+=k：从l位置往后所有前缀和全部增加k
//2.b[r+1]-=k：从r+1位置往后抵消增加的k，保证r之后数值不变
//最终仅区间[l,r]内所有元素统一加上k，单次修改仅2次操作O(1)
b[l]+=k;
b[r+1]-=k;
}
for(int i=1;i<=n;i++){
a[i]=a[i–1]+b[i];//这里记得要加和回去进行前缀和变为原数组
}
for(int i=1;i<=n;i++){
out.print(a[i]);//格式化输出
if(i!=n) out.print(" ");
}
out.flush();
out.close();
br.close();
}
}

所以基于这个原理，我们在创建树状数组的时候就应该初始化原数组的差分形式，在单点求值求值的时候就直接进行一个前缀和操作（对应树状数组的query方法）就可以了，而区间增加一个量就按上面这个差分的操作(对应树状数组的add方法)，这道题就可以解了：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 500010;
static ll Tree[N];
static ll n, m;
static ll lowbit(ll x) {
return x & (–x);
}
static void add(ll x, ll v) {
while (x <= n) {
Tree[x] += v;
x += lowbit(x);
}
}
static ll query(ll x) {
ll res = 0;
while (x > 0) {
res += Tree[x];
x -= lowbit(x);
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
add(i, a[i] – a[i – 1]);//初始化的是原数组的差分形式
}
while (m—) {
int op;
cin >> op;
if (op == 1) {
int x, y, k;
cin >> x >> y >> k;
//和上面代码一样，以差分的方式对区间求值
add(x, k);
add(y + 1, –k);
} else {
int x;
cin >> x;
cout << query(x) << "\\n";//差分求和就是原数组
}
}
return 0;
}

2.区间增值和区间求和

其实这个问题对于树状数组来说有难度，引用洛谷P3372线段数模版，在这里我会有三种不同的解法，但不是每一种都合适，也不是每一种都能解这个题：

引用洛谷P3372 【模板】线段树 1

题目链接如下： 洛谷P3372 在这里我们先不去想线段树的解法，在看到这个题目的要求，要我们实现区间增值和区间求和，能想到啥，前缀和和差分的结合不就能实现了吗，那怎么加在一起？以上面的树状数组为载体就可以了

解法一.树状数组暴力解法

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAX=1000010;
static ll Tree[MAX];
static ll sum[MAX];
static int n,m;
static int lowbit(int x) {
return x&(–x);
}
static void add1(int x,int v) {
while (x<=n) {
Tree[x]+=v;
x+=lowbit(x);
}
}
static ll query(int x) {
ll res=0;
while (x>0) {
res+=Tree[x];
x-=lowbit(x);
}
return res;
}
ll get_sum(int x){//这里实现了一个对差分和再求和的过程，即求前缀和
sum[0] = 0;
for(int i=1;i<=x;i++){
sum[i] = sum[i–1] + query(i);
}
return sum[x];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>m;
vector<int> a(n+1, 0);
for (int i = 1; i <= n; i++) {
cin>>a[i];
add1(i, a[i] – a[i–1]);//也是传入它的差分形式
}
while (m—) {
int op;
cin >> op;
if (op == 1) {
int L, R, k;
cin >> L >> R >> k;
//这里和前面差分的逻辑是一样的
add1(L, k);
add1(R+1, –k);
}else {
int L,R;
cin >> L >> R;
ll total = get_sum(R) – get_sum(L–1);//前缀和的标准操作
cout << total << '\\n';
}
}
return 0;
}

理论上，这种解法是对的，但是，在考虑时间复杂度的时候就不行了，它的时间复杂度如下：

所以可想而知，我们这个代码的时间复杂度不是我们想要的O(logn),且它过不了这个题的，如果提交就是如下结果: 很显然是超时了的，时间复杂度太大了。

所以很显然我们要对它进行优化：

解法二.双树状数组模拟解法

在使用这个解法前，我们先思考一下：对于树状数组来说，要解这个题,还是前缀和和差分的结合，但我们要优化，推导过程如下：

一、基础定义

设原数组

a

[

1

…

n

]

a[1\\dots n]

a[1…n]，规定

a

0

=

0

a_0=0

a0​=0 差分数组

b

[

1

…

n

]

b[1\\dots n]

b[1…n]：

b

i

=

a

i

−

a

i

−

1

b_i = a_i – a_{i-1}

bi​=ai​−ai−1​

设

c

[

k

]

c[k]

c[k] 为差分数组

b

b

b 的前缀和：

c

[

k

]

=

∑

i

=

1

k

b

i

=

b

1

+

b

2

+

⋯

+

b

k

c[k] = \\sum_{i=1}^k b_i = b_1 + b_2 + \\dots + b_k

c[k]=i=1∑k​bi​=b1​+b2​+⋯+bk​

二、步骤1：证明差分数组前缀和 $c[k]=a_k$

将

b

i

=

a

i

−

a

i

−

1

b_i = a_i – a_{i-1}

bi​=ai​−ai−1​ 代入展开：

c

[

k

]

=

b

1

+

b

2

+

b

3

+

⋯

+

b

k

=

(

a

1

−

a

0

)

+

(

a

2

−

a

1

)

+

(

a

3

−

a

2

)

+

⋯

+

(

a

k

−

a

k

−

1

)

\\begin{aligned} c[k] &= b_1 + b_2 + b_3 + \\dots + b_k \\\\ &= (a_1-a_0) + (a_2-a_1) + (a_3-a_2) + \\dots + (a_k – a_{k-1}) \\end{aligned}

c[k]​=b1​+b2​+b3​+⋯+bk​=(a1​−a0​)+(a2​−a1​)+(a3​−a2​)+⋯+(ak​−ak−1​)​ 裂项全部抵消，

a

0

=

0

a_0=0

a0​=0：

c

[

k

]

=

a

k

c[k] = a_k

c[k]=ak​ 等价关系：

∑

i

=

1

k

b

i

=

a

k

\\sum_{i=1}^k b_i = a_k

i=1∑k​bi​=ak​

三、步骤2：推导原数组前 $k$

把

a

i

=

∑

t

=

1

i

b

t

a_i = \\sum_{t=1}^i b_t

ai​=∑t=1i​bt​ 代入总和公式：

S

(

k

)

=

∑

i

=

1

k

a

i

=

∑

i

=

1

k

(

∑

t

=

1

i

b

t

)

S(k) = \\sum_{i=1}^k a_i = \\sum_{i=1}^k \\left( \\sum_{t=1}^i b_t \\right)

S(k)=i=1∑k​ai​=i=1∑k​(t=1∑i​bt​)

交换二重求和顺序

b

t

b_t

bt​ 在

i

=

t

,

i

=

t

+

1

,

…

,

i

=

k

i=t,i=t+1,\\dots,i=k

i=t,i=t+1,…,i=k 中一共出现

k

−

t

+

1

k-t+1

k−t+1 次：

S

(

k

)

=

∑

t

=

1

k

b

t

⋅

(

k

−

t

+

1

)

=

∑

t

=

1

k

b

t

⋅

[

k

−

(

t

−

1

)

]

=

∑

t

=

1

k

[

k

⋅

b

t

−

(

t

−

1

)

⋅

b

t

]

\\begin{aligned} S(k) &= \\sum_{t=1}^k b_t \\cdot (k – t + 1) \\\\ &= \\sum_{t=1}^k b_t \\cdot \\big[ k – (t-1) \\big] \\\\ &= \\sum_{t=1}^k \\Big[ k\\cdot b_t – (t-1)\\cdot b_t \\Big] \\end{aligned}

S(k)​=t=1∑k​bt​⋅(k−t+1)=t=1∑k​bt​⋅[k−(t−1)]=t=1∑k​[k⋅bt​−(t−1)⋅bt​]​

拆分求和项

S

(

k

)

=

k

⋅

∑

t

=

1

k

b

t

−
  

∑

t

=

1

k

(

t

−

1

)

⋅

b

t

S(k) = k\\cdot \\sum_{t=1}^k b_t \\;-\\; \\sum_{t=1}^k (t-1)\\cdot b_t

S(k)=k⋅t=1∑k​bt​−t=1∑k​(t−1)⋅bt​

四、最终结论

原数组前

k

k

k 项累加和公式：

a

1

+

a

2

+

⋯

+

a

k

=

k

⋅

∑

i

=

1

k

b

i

−
  

∑

i

=

1

k

(

i

−

1

)

⋅

b

i

\\boldsymbol{a_1+a_2+\\dots+a_k = k \\cdot \\sum_{i=1}^k b_i \\;-\\; \\sum_{i=1}^k (i-1)\\cdot b_i}

a1​+a2​+⋯+ak​=k⋅i=1∑k​bi​−i=1∑k​(i−1)⋅bi​

所以基于以上推导过程，我们要添加几个方法： 以下为左神上课原图（上面的sum方法其实就是模版里的query方法）： 通俗一点来说我们要求l~r范围内的累加和就是先去维护一个方法query(求1 ~k的累加和），l ~r的累加和就是query（1-r）-query(1-(l-1)),，就是图中的range方法，而要区间增值，其实也是和差分是一样的，照着公式来说：

a

1

+

a

2

+

⋯

+

a

k

=

k

⋅

∑

i

=

1

k

b

i

−
  

∑

i

=

1

k

(

i

−

1

)

⋅

b

i

\\boldsymbol{a_1+a_2+\\dots+a_k = k \\cdot \\sum_{i=1}^k b_i \\;-\\; \\sum_{i=1}^k (i-1)\\cdot b_i}

a1​+a2​+⋯+ak​=k⋅i=1∑k​bi​−i=1∑k​(i−1)⋅bi​

差分我修改的话就要分两个部分来修改(就和上图一样)，正好对应了我们设出的两个树状数组，所以代码如下： java代码：

import java.io.*;
import java.util.*;
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(System.out);
static StringTokenizer st;
final static long MAX=1000010;
// Tree1：维护差分数组b[i]的前缀和 Σb[i]
static long []Tree1;
// Tree2：维护 (i-1)*b[i] 的前缀和 Σ(i-1)*b[i]
static long []Tree2;
static int n,m;
public static int lowbit(int x){
return x&(–x);
}
// 单点更新两棵树：差分数组x位置增加v
public static void update(int x,long v){
// 循环向上更新所有包含x的区间节点
for(int i=x;i<MAX;i+=lowbit(i)){
Tree1[i]+=v;
// Tree2对应存入 (x-1)*v，和前面的推导公式相同
Tree2[i]+=(x–1)*v;
}
}
// 区间 [l,r] 整体加上数值v，进行一个差分的操作
public static void RangeAdd(int l,int r,long v){
update(l,v); // l位置增量v，l之后全部+ v
update(r+1,–v); // r+1位置减v，这样就可以抵消增量，而且仅l~r生效
}
// 查询原数组前x项总和，套用前面推出来的公式 S(x) = x*Σb[i] – Σ(i-1)*b[i]
public static long getSum(int x){
long res1=0; // 存储Tree1前缀和 Σb[i]
long res2=0; // 存储Tree2前缀和 Σ(i-1)*b[i]
// 从x往左拆分区间累加
for(int i=x;i>0;i-=lowbit(i)){
res1+=Tree1[i];
res2+=Tree2[i];
}
return res1*x–res2;
}
// 查询任意区间 [l,r] 的累加和
// 区间和 = 前r项总和 – 前l-1项总和
public static long RangeQuery(int l,int r){
return getSum(r)–getSum(l–1);
}
public static void main(String[] args) throws IOException{
st=new StringTokenizer(br.readLine());
n=Integer.parseInt(st.nextToken());
m=Integer.parseInt(st.nextToken());
//Math.toIntExact方法是用于将Long转为int,其实也可以(int)来强转的
Tree1=new long[Math.toIntExact(MAX)];
Tree2=new long[Math.toIntExact(MAX)];
st=new StringTokenizer(br.readLine());
for(int i=1;i<=n;i++){
long num=Long.parseLong(st.nextToken());
// 单点赋值就是相当于在区间[i,i]都增加num
RangeAdd(i,i,num);
}
while(m— > 0){
st=new StringTokenizer(br.readLine());
int op=Integer.parseInt(st.nextToken());
if(op==1){
int l=Integer.parseInt(st.nextToken());
int r=Integer.parseInt(st.nextToken());
long k=Long.parseLong(st.nextToken());
RangeAdd(l,r,k);
}else{
int l=Integer.parseInt(st.nextToken());
int r=Integer.parseInt(st.nextToken());
out.println(RangeQuery(l,r));
}
}
out.flush();
out.close();
br.close();
}
}

C++代码：

//和Java的逻辑相同
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAX=1000010;
ll Tree1[MAX];
ll Tree2[MAX];
static int n,m,op;
static int lowbit(int x) {
return x&(–x);
}
static void update(int x,ll v) {
for (int i = x; i <= n; i+=lowbit(i)) {
Tree1[i]+=v;
Tree2[i]+=v*(x–1);
}
}
static void RangeAdd(int l,int r,ll v) {
update(l,v);
update(r+1,–v);
}
static ll getSum(int x) {
ll res1=0;
ll res2=0;
for (int i = x; i > 0; i-=lowbit(i)) {
res1+=Tree1[i];
res2+=Tree2[i];
}
return res1*x–res2;
}
static ll RangeQuery(int l,int r) {
return getSum(r)–getSum(l–1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>m;
for (int i = 1; i <= n; i++) {
ll num;
cin>>num;
RangeAdd(i,i,num);
}
while (m—) {
cin>>op;
if (op==1) {
int l,r;
ll k;
cin>>l>>r>>k;
RangeAdd(l,r,k);
}else {
int l,r;
cin>>l>>r;
cout<<RangeQuery(l,r)<<"\\n";
}
}
return 0;
}

所以对于我们双树状数组的解法来说它的时间复杂度为：

对比这个和上面那个写法来说，它的时间就大大缩小了。

解法三.线段树经典解法

在这里不仔细说明线段树的原理了，其实线段树就是一种二叉树，对于树状数组在解题时遇到不可查分信息时，树状数组往往思路复杂，这个时候线段树就挺身而出了，它的原理是基于分治递归来的，就是说我维护一个二叉树，对于叶子节点就存单个元素，而非叶子节点就存这段区间的总和以及最值等信息，而子节点数值更新后，和大多数二叉树一样，父节点的值 = 左子节点 + 右子节点，在区间修改的时候，我们就会用到懒标记，其实就是能不往下更新就先不更新，延迟下放的一个操作，所以代码如下： java代码如下：

//线段树代码的实现
import java.io.*;
import java.util.*;
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(System.out);
static StringTokenizer st;
final static int MAX=1000010;
// 表示线段树数组：存储每个区间的总和，开4倍空间防止越界
static long[] tree;
// 表示懒标记数组：保存待下传的区间增量，延迟更新子节点
static long[] lazy;
static int n,m;
public static void pushUp(int node){//这个方法其实是用于向上合并节点的
tree[node] = tree[node*2] + tree[node*2+1];
}
public static void pushDown(int node,int l,int r){
// 没有待下放增量的操作的话，就直接返回无需操作
if(lazy[node]==0) return;
int mid = (l+r)/2;
int left = node*2; // 左孩子节点编号
int rightNode = node*2+1; // 右孩子节点编号
// 更新左子树总和与懒标记
tree[left] += lazy[node] * (mid – l + 1);
lazy[left] += lazy[node];
// 更新右子树总和与懒标记
tree[rightNode] += lazy[node] * (r – mid);
lazy[rightNode] += lazy[node];
// 当前节点标记已下放，清空懒标记
lazy[node] = 0;
}
public static void build(int node,int l,int r,long[] a){
// 叶子节点，对应原数组单个元素，直接赋值
if(l == r){
tree[node] = a[l];
return;
}
int mid = (l+r)/2;
// 递归构造左子树 [l,mid]
build(node*2, l, mid, a);
// 递归构造右子树 [mid+1,r]
build(node*2+1, mid+1, r, a);
// 左右子树构造完成，更新当前节点区间和
pushUp(node);
}
public static void RangeAdd(int node,int l,int r,int L,int R,long v){
// 当前区间完全被修改区间包含，直接打懒标记返回
if(L<=l && r<=R){
tree[node] += v * (r – l + 1);
lazy[node] += v;
return;
}
// 不完全包含，先下放旧标记再递归子节点
pushDown(node, l, r);
int mid = (l+r)/2;
// 左区间有重叠，递归修改左子节点
if(L <= mid) RangeAdd(node*2, l, mid, L, R, v);
// 右区间有重叠，递归修改右子节点
if(R > mid) RangeAdd(node*2+1, mid+1, r, L, R, v);
// 子节点修改完成，更新当前节点总和
pushUp(node);
}
public static long RangeQuery(int node,int l,int r,int L,int R){
// 当前区间完全在查询范围内，直接返回区间和
if(L<=l && r<=R){
return tree[node];
}
// 访问子节点前下放懒标记，保证数据正确
pushDown(node, l, r);
int mid = (l+r)/2;
long res = 0;
// 左区间存在查询范围，累加左子树结果
if(L <= mid) res += RangeQuery(node*2, l, mid, L, R);
// 右区间存在查询范围，累加右子树结果
if(R > mid) res += RangeQuery(node*2+1, mid+1, r, L, R);
return res;
}
public static void main(String[] args) throws IOException{
st=new StringTokenizer(br.readLine());
n=Integer.parseInt(st.nextToken());
m=Integer.parseInt(st.nextToken());
// 初始化线段树与懒标记数组，4倍空间
tree = new long[MAX * 4];
lazy = new long[MAX * 4];
// 存储原始输入数组，下标从1开始
long[] a = new long[n+1];
st=new StringTokenizer(br.readLine());
for(int i=1;i<=n;i++){
a[i]=Long.parseLong(st.nextToken());
}
// 根节点编号1，构建1~n的线段树
build(1, 1, n, a);
while(m— > 0){
st=new StringTokenizer(br.readLine());
int op=Integer.parseInt(st.nextToken());
if(op==1){
int l=Integer.parseInt(st.nextToken());
int r=Integer.parseInt(st.nextToken());
long k=Long.parseLong(st.nextToken());
RangeAdd(1,1,n,l,r,k);
}else{
int l=Integer.parseInt(st.nextToken());
int r=Integer.parseInt(st.nextToken());
out.println(RangeQuery(1,1,n,l,r));
}
}
out.flush();
out.close();
br.close();
}
}

C++代码如下：

//逻辑和Java的相同
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 1000010;
ll tree[MAX * 4];
ll lazy[MAX * 4];
int n, m;
void pushUp(int node) {
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
void pushDown(int node, int l, int r) {
if (lazy[node] == 0) return;
int mid = (l + r) / 2;
int left = node * 2;
int rightNode = node * 2 + 1;
tree[left] += lazy[node] * (mid – l + 1);
lazy[left] += lazy[node];
tree[rightNode] += lazy[node] * (r – mid);
lazy[rightNode] += lazy[node];
lazy[node] = 0;
}
void build(int node, int l, int r, ll a[]) {
if (l == r) {
tree[node] = a[l];
return;
}
int mid = (l + r) / 2;
build(node * 2, l, mid, a);
build(node * 2 + 1, mid + 1, r, a);
pushUp(node);
}
void RangeAdd(int node, int l, int r, int L, int R, ll v) {
if (L <= l && r <= R) {
tree[node] += v * (r – l + 1);
lazy[node] += v;
return;
}
pushDown(node, l, r);
int mid = (l + r) / 2;
if (L <= mid) RangeAdd(node * 2, l, mid, L, R, v);
if (R > mid) RangeAdd(node * 2 + 1, mid + 1, r, L, R, v);
pushUp(node);
}
ll RangeQuery(int node, int l, int r, int L, int R) {
if (L <= l && r <= R) {
return tree[node];
}
pushDown(node, l, r);
int mid = (l + r) / 2;
ll res = 0;
if (L <= mid) res += RangeQuery(node * 2, l, mid, L, R);
if (R > mid) res += RangeQuery(node * 2 + 1, mid + 1, r, L, R);
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
ll *a = new ll[n + 1];
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
build(1, 1, n, a);
delete[] a;
while (m— > 0) {
int op;
cin >> op;
if (op == 1) {
int l, r;
ll k;
cin >> l >> r >> k;
RangeAdd(1, 1, n, l, r, k);
} else {
int l, r;
cin >> l >> r;
cout << RangeQuery(1, 1, n, l, r) << '\\n';
}
}
return 0;
}

所以从这里来看，线段树的代码量更为巨大，而它的时间复杂度为：

因此和树状数组的时间复杂度大致相同，但它们有啥区别呢，为啥说树状数组不适合用于解不可差分信息呢？其实很好理解，树状数组其实本质上是和前缀和，差分有一样的思想，就是说： 树状数组的所有操作，建立在两条特性： 修改是靠单点增量； 查询是前缀合并**，且合并运算满足： f(1∼x)=f(1∼mid)+f(mid+1∼x) 加法、求和满足这个，属于可差分信息： 原数组区间和可以拆差分，区间修改也能用差分两点更新实现。 因此像区间最大值、区间最小、区间 GCD这些不可差分信息，他就无法简单的实现了。

3.二进制区间取反与单点求值

引用：牛客PEEK75 区间取反与单点求值

题目链接如下： 牛客PEEK区间取反和单点求值

我一开始看到这个题目还以为是区间正数变为负数，负数变为正数，看错了题目，其实它是给我们一个长度为n的字符串（只包括0和1），然后要我们去查询那个位置是0还是1，翻转的话就是把范围l~r范围内的字符由0改为1，由1改为0，那翻转其实就是对它进行一个异或操作就行了，在这里也还是要用到差分的思想，就对原区间进行异或，就对差分后的两头分别异或就行了，所以代码如下： java代码如下：

import java.io.*;
import java.util.*;
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(System.out);
static StringTokenizer st;
static int n,m;
static int []Tree;
static int []a;
public static int lowbit(int x){//和树状数组一样是取最右位的1
return x&(–x);
}
public static void add(int x,int v) {//这里是一个异或的思想
for(int i=x;i<=n;i+=lowbit(i)){//和树状树组模板一样，去找它管的下标
Tree[i]^=v;//不断异或就能实现它的翻转
}
}
public static int query(int x){//这里则为向下遍历，累加前缀所有翻转标记，就是一个异或叠加的过程
int res=0;
for(int i=x;i>0;i-=lowbit(i)){
res^=Tree[i];
}
return res;
}
public static void main(String[] args) throws Exception {
st=new StringTokenizer(br.readLine());
n=Integer.parseInt(st.nextToken());
m=Integer.parseInt(st.nextToken());
String s=br.readLine().trim();
a=new int[n+1];
Tree=new int[n+1];
// 将下标1~n的输入的01字符串存入数组a
for(int i=1;i<=n;i++){
a[i]=s.charAt(i–1)–'0';
}
while(m— > 0){
st=new StringTokenizer(br.readLine());
int op=Integer.parseInt(st.nextToken());
if(op==1){
int l=Integer.parseInt(st.nextToken());
int r=Integer.parseInt(st.nextToken());
//类似于差分的异或差分：l位置打翻转标记，r+1位置抵消后面的翻转就可以了
add(l,1);
add(r+1,1);
}else{
int x=Integer.parseInt(st.nextToken());
//原始数字 ^ 总翻转次数，就可以得到翻转后的结果了
out.println(a[x]^query(x));
}
}
out.flush();
out.close();
br.close();
}
}

C++代码如下：

//和Java代码的逻辑相同
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> Tree;
vector<int> a;
static int lowbit(int x) {
return x & –x;
}
static void add(int x, int k) {
for (int i = x; i <= n; i += lowbit(i)) {
Tree[i] ^= k;
}
}
static int query(int x) {
int res = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
res ^= Tree[i];
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int m;
cin >> n >> m;
string s;
cin >> s;
a.resize(n + 1);
Tree.resize(n + 1, 0);
for (int i = 0; i < n; ++i) {
a[i + 1] = s[i] – '0';
}
while (m—) {
int op;
cin >> op;
if (op == 1) {
int l, r;
cin >> l >> r;
add(l, 1);
add(r + 1, 1);
} else {
int x;
cin >> x;
cout << (a[x] ^ query(x)) << "\\n";
}
}
return 0;
}