# Go 树状数组-各种板子

**Repository Path**: hoemfei/BitTree

## Basic Information

- **Project Name**: Go 树状数组-各种板子
- **Description**: 包括区间更新-区间查询
- **Primary Language**: Go
- **License**: Zlib
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-01-18
- **Last Updated**: 2022-06-15

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Go 树状数组-板子

#### 介绍
### 代码中无论1，2，3 所有操作都是 是根据原数组下标从0开始到len-1 的操作
### 但是树状数组是从 1 到 len，我开辟树状数组的空间是原数组的大小+1
### 网上的都是从 1到 len 的操作，我这里是(0 到 len-1)对原数组操作，注意这点即可

1. 单点修改-区间查询和（easy :tw-1f603:）
2. 区间修改-单点查询 (然并卵的操作:-1:) 
3. 区间修改-区间查询 （主要介绍这个 :heart_eyes: 理解了代码比懒标记线段树代码简短）

- 原数组:  a [i], 每一个元素的值
- 差分数组:b [i], 下标 i 的元素存放 a[i]-a[i-1] 的差值，b[1]=a[1]
- **我们可以得到下面的公式:**
```
    a[1] + a[2] + ... + a[n] = (b[1]) + (b[1]+b[2]) + (b[1]+b[2]+b[3]) + ... + (b[1]+b[2]+...+b[n])
                             ✔对上面的式子提取公因式，得以下

                             = n * b[1] + (n - 1) * b[2] + (n - 2) * b[3] + ... + b[n] 
                             ✔ 对上面的式子 +((i-1)*b[i])  -((i-1)*b[i]), (i从1递增到n) 提取公因式，得以下

                             = n * (b[1] + b[2] + ... + b[n]) - (0*b[1] + 1*b[2] + 2*b[3] + ... + (n-1)*b[n]) 
                             ✔ 对上面的式子 +b[i]  -b[i], (i从1递增到n) 得以下

                             = (n+1)(b[1] + b[2] + ... + b[n]) - (1*b[1] + 2*b[2] + 3*b[3] + ... + n*b[n])
                      n              n        n
                      ∑ a[i] = (n+1)*∑ b[i] - ∑ i*b[i]
                     i=1            i=1      i=1
```
- **差分数组和原数组 的核心公式 :point_up:**
![输入图片说明](%E5%BE%AE%E4%BF%A1%E5%9B%BE%E7%89%87_20220120172047.jpg)
- a[i]  数组表示原数组
- b1[i] 数组表示:b1[i] = a[i]-a[i-1], 差分数组
- b2[i] 数组表示:b2[i] = i * b1[i]
- c1[i] 针对 b1 的树状数组
- c2[i] 针对 b2 的树状数组
![输入图片说明](bitTree.png)
![输入图片说明](bitTree2.png)