树状数组求区间和的一些常见模型

树状数组区间求和树状数组是一种用于高效求解区间和的数据结构。

它可以在O(log n)的时间复杂度内完成单点更新和区间求和操作，比传统的数组操作要快得多。

本文将介绍树状数组的原理、实现以及应用场景。

一、树状数组的原理树状数组的原理基于二进制的思想。

假设有一个长度为n的数组a，我们可以将其转化为一个长度为n的树状数组c。

树状数组的每个节点存储了一段原数组的区间和。

树状数组中的每个节点的编号i 代表的是原数组中的第1个到第i个元素的区间和。

树状数组的构建过程如下：1. 初始化树状数组c，将其所有元素置为0。

2. 对于原数组a的每个元素a[i]，更新树状数组c的节点c[i]，使其加上a[i]。

3. 根据树状数组的性质，每个节点c[i]存储的是原数组a中从i 到i-lowbit(i)+1的区间和。

二、树状数组的实现树状数组的实现需要定义三个关键操作：求和操作、单点更新操作和区间求和操作。

1. 求和操作：从树状数组的根节点开始，不断向左子节点或者右子节点移动，直到达到叶子节点。

叶子节点存储的就是所求区间的和。

2. 单点更新操作：从待更新的节点开始，不断向根节点移动，每次移动时更新当前节点的值。

这样可以保持树状数组的正确性。

3. 区间求和操作：分别求出右边界的区间和和左边界-1的区间和，然后相减，即可得到所求区间的和。

三、树状数组的应用场景树状数组的高效性使得它在很多场景下被广泛应用。

1. 区间求和：树状数组可以高效地求解数组中任意区间的和，比如求解某个区间内的元素和、计算前缀和等。

2. 单点更新：树状数组可以高效地对单个元素进行更新，比如修改某个元素的值或者增加某个元素的数量。

3. 逆序对个数：树状数组可以高效地统计给定数组中逆序对的个数，即后面的元素比前面的元素大的情况。

4. 数组去重：树状数组可以高效地对一个数组进行去重操作，找出数组中的不重复元素。

5. 数组排序：树状数组可以高效地对一个数组进行排序，将数组中的元素按照某个规则重新排列。

用树状数组解决区间查询问题分享自斯里猫: 本文扩写自郭神的《树状数组新应用》，在此表示膜拜。

树状数组的学名貌似叫做Binary Index Tree，关于它的基本应用可参考Topcoder上的这篇Tutorial.树状数组可以看作一个受限制的线段树，它维护一个数组，最经典的树状数组支持的基本操作有两个：(1)改变某一个元素的值(2)查询某一个区间内所有元素的和。

在此基础上，经过简单的变形可以变成支持另一组操作：(1)把一个区间内所有元素都加上一个值(2)查询某一个元素的值。

这两个都是已经泛滥了的东西了，在此不赘述。

简单的树状数组模型是不支持这样一组操作的：(1)把某一个区间内所有元素都加上一个值(2)查询某一个区间内所有元素的和。

当然，这个东西可以用线段树完成，但是线段树占内存比较大，写起来也比较繁（对我这种不会数据结构的人而言）。

下面我们用一个改进版的树状数组完成这个任务。

首先一个观察是区间操作总可以变成从最左端开始，比如把区间[3..6]都加10，可以变成[1..6]加10, [1..2]减10。

查询也类似。

于是下面只关心从最左端开始的情况。

定义Insert(p, d)表示把区间[1..p]都加d，Query(p)表示查询区间[1..p]之和。

我们考虑调用一次Insert(p, d)对以后的某次查询Query(q)的影响：(1) 如果p<=q，总的结果会加上p*d (2) 如果p>q，总的结果会加上q*d也就是说，Query(q)的结果来源可分为两部分，一部分是Insert(p1,d) (p1<=q)，一部分是Insert(p2,d) (p2 > q)。

我们用两个数组B[], C[]分别维护这两部分信息，B[i]表示区间右端点恰好是i的所有区间的影响之和，C[i]表示区间右端点大于i的所有区间的影响之和。

每当遇到Insert时，考虑当前的Insert会对以后的Query产生什么影响，更新B和C数组；当遇到Query时，把两部分的结果累加起来。

树状数组的操作树状数组的⼀些基本操作。

树状数组⽀持单点修改和查询区间和的操作，但和线段树不同，它不⽀持区间修改操作（有些题⽬可以将区间修改转化为单点修改，有些则不可以）。

下⾯介绍树状数组的预处理和基本操作。

1.求lowbit(n)上⼀篇博客介绍了lowbit的定义和使⽤定义的基本求法。

但是依据定义求lowbit未免⿇烦。

因⽽，求lowbit需要导⼊公式：lowbit(n)=n&(-n)。

求lowbit函数：int lowbit(int n){//求n的lowbitreturn n&(-n);}2.对某个元素进⾏加法操作根据树状数组的性质，对于任意⼀个结点x，只有结点c[x]及其祖先结点保存的区间和中含a[x]，所以我们只需要对x不断向上搜索即可。

代码：void update(int x,int y){//将x位置元素加上yfor(;x<=N;x+=lowbit(x){//依次寻找x的⽗节点c[x]+=y;//进⾏更新}}这⾥在寻找x的⽗节点时运⽤了上⼀篇博客中的性质③（具体的证明⽅法我也不会qwq）。

举例证明：假设我们要对A[2]进⾏加x的操作。

2的lowbit值为2，则第⼀步2变成了4，对C[4]进⾏处理。

4的lowbit值为4，则第⼆步变成了8，对C[8]进⾏处理。

此时已到达循环边界。

再假设我们要对A[5]进⾏加x的操作。

5的lowbit值为1，则第⼀步5变成了6，对C[6]进⾏处理。

6的lowbit值为2，则第⼆步变成了8，对C[8]进⾏处理。

此时已到达循环边界。

3.查询前缀和操作前缀和的求法：求出x的⼆进制表⽰中每个等于1的位，把[1,x]分成logN个⼩区间，⽽每个⼩区间的区间和已保存在数组c中。

代码（我也不会证）：int sum(int x){//求1~x的区间和int ans=0;for(;x;x-=lowbit(x);){ans+=c[x];}return ans;}举例证明：假设我们要求A[6]的前缀和。

第01讲什么是树状数组？树状数组用来求区间元素和，求一次区间元素和的时间效率为O(logn)。

有些同学会觉得很奇怪。

用一个数组S[i]保存序列A[]的前i个元素和，那么求区间i,j的元素和不就为S[j]-S[i-1]，那么时间效率为O(1)，岂不是更快？但是，如果题目的A[]会改变呢？例如：我们来定义下列问题：我们有n个盒子。

可能的操作为1.向盒子k添加石块2.查询从盒子i到盒子j总的石块数自然的解法带有对操作1为O(1)而对操作2为O(n)的时间复杂度。

但是用树状数组，对操作1和2的时间复杂度都为O(logn)。

第02讲图解树状数组C[]现在来说明下树状数组是什么东西？假设序列为A[1]~A[8]网络上面都有这个图，但是我将这个图做了2点改进。

（1）图中有一棵满二叉树，满二叉树的每一个结点对应A[]中的一个元素。

（2）C[i]为A[i]对应的那一列的最高的节点。

现在告诉你：序列C[]就是树状数组。

那么C[]如何求得？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];以上只是枚举了所有的情况，那么推广到一般情况，得到一个C[i]的抽象定义：因为A[]中的每个元素对应满二叉树的每个叶子，所以我们干脆把A[]中的每个元素当成叶子，那么：C[i]=C[i]的所有叶子的和。

现在不得不引出关于二进制的一个规律：先仔细看下图：将十进制化成二进制，然后观察这些二进制数最右边1的位置：1 --> 000000012 --> 000000103 --> 000000114 --> 000001005 --> 000001016 --> 000001107 --> 000001118 --> 000010001的位置其实从我画的满二叉树中就可以看出来。

利用树状数组解决几类问题树状数组作为一种实现简单、应用较广的高级数据结构，在OI 界的地位越来越重要，下面我来简单介绍一下树状数组和它的简单应用。

一、树状数组简介树状数组(Binary Indexed Trees ，简称BIT)是一种特殊的数据结构，这种数据结构的时空复杂度和线段树相似，但是它的系数要小得多。

它可以方便地查询出一段区间中的数字之和。

其查询和修改的时间复杂度均为O(lbN),并且是一个在线的数据结构，可以随时修改并查询。

我接下来用一道题目来介绍树状数组的几个基本操作。

【引例】假设有一列数{A i }（1<=i<=n ），支持如下两种操作： 1. 将A k 的值加D 。

（k ，D 是输入的数）2. 输出∑=tsi i A （s ，t 都是输入的数，s<=t ）这道题目用线段树很容易可以解决，我就不多说了，那么如何用树状数组来解决呢？我们新增一个数组C[]，其中C[i]=a[i-2k+1]+……+a[i](k 为i 在二进制形式下末尾0的个数)。

低位技术，也叫Lowbit(k)。

对于Lowbit 这里我提三种不同的写法（这三种形式是等价的，读者有兴趣可以去证明一下）：1.Lowbit(k)=k and (k or (k-1))2.Lowbit(k)=k and not (k-1)3.Lowbit(x)=k and –k然后我来分析引例的树状数组解法，为了可以更好地理解这种方法，读者可以根据以下这幅图来加以理解。

【操作2】修改操作：将A k 的值加D可以从C[i]往根节点一路上溯，调整这条路上的所有C[]即可，这个操作的复杂度在最坏情况下就是树的高度即O(lbN)。

定理1：若A[k]所牵动的序列为C[p 1]，C[p 2]……C[p m ]， 则p 1=k ，而ili i p p 21+=+（l i 为p i 在二进制中末尾０的个数）。

例如A[1]……A[8]中，a[3] 添加x ； p 1=k=3 p 2=3+20=4 p 3=4+22=8 p 4=8+23=16>8由此得出，c[3]、c[4]、c[8]亦应该添加x 。

树状数组的模板题【如果你不知道什么是树状数组：这是⼀道模板题。

给定数列a1,a2,…,a n，你需要进⾏m各操作，操作有两类：1 i x：给定i,x，将a i加上x；2 l r：给定l.r，求Σr i=l a i的值（换⾔之，求a l+a l+1+⋯+a r的值）。

输⼊格式第⼀⾏包含2个正整数n,m，表⽰数列长度和询问个数。

保证1≤n,m≤106。

第⼆⾏n个整数a1,a2,…,a n，表⽰初始数列。

保证|a i|≤106。

接下来m⾏，每⾏⼀个操作，为以下两种之⼀：1 i x：给定i,x，将a i加上x；2 l r：给定l.r，求Σr i=l a i的值。

保证1≤l≤r≤n,|x|≤106。

输出格式对于每个2 l r操作输出⼀⾏，每⾏有⼀个整数，表⽰所求的结果。

思路：这是⼀道简单的⼀维树状数组的模板题#include <bits/stdc++.h>using namespace std;typedef long long ll;#define endl '\n'#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);#define _for(i, a, b) for (int i=(a); i<=(b); i++)const int INF = 0x7fffffff;const int MAXN = 1e6 + 10;ll tree[MAXN], n, m;inline ll lowbit(ll x){return x & (-x);}void updata(ll x, ll d){while(x <= n){tree[x] += d;x += lowbit(x);}}ll getsum(ll x){ll res = 0;while(x > 0){res += tree[x];x -= lowbit(x);}return res;}int main(){IOScin >> n >> m;_for(i, 1, n){ll a;cin >> a;updata(i,a);}while(m--){ll id, x, y;cin >> id >> x >> y;if(id == 1){updata(x,y);}else if(id == 2){cout << getsum(y) - getsum(x-1) << endl;}}return 0;}这是⼀道模板题。

树状数组是一个查询和修改复杂度都为log(n)的数据结构，假设数组a[1..n]，那么查询a[1]+...+a[n]的时间是log级别的，而且是一个在线的数据结构，支持随时修改某个元素的值，复杂度也为log级别。

来观察这个图：令这棵树的结点编号为C1，。

令每个结点的值为这棵树的值的总和，那么容易发现：C1 = A1C2 = A1 + A2C3 = A3 C4 = A1 + A2 + A3 + A4C5 = A5C6 = A5 + A6C7 = A7C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8...C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16这里有一个有趣的性质：设节点编号为x，那么这个节点管辖的区间为2^k（其中k为x二进制末尾0的个数）个元素。

因为这个区间最后一个元素必然为Ax，所以很明显：Cn = A(n –2^k + 1) + ... + An算这个2^k有一个快捷的办法，定义一个函数如下即可：int lowbit(int x){return x&(x^(x–1));}当想要查询一个SUM(n)(求a[n]的和），可以依据如下算法即可：step1:令sum = 0，转第二步；step2:假如n <= 0，算法结束，返回sum值，否则sum = sum + Cn，转第三步；step3: 令n = n –lowbit(n)，转第二步。

可以看出，这个算法就是将这一个个区间的和全部加起来，为什么是效率是log(n)的呢？以下给出证明：n = n –lowbit(n)这一步实际上等价于将n的二进制的最后一个1减去。

而n的二进制里最多有log(n)个1，所以查询效率是log(n)的。

那么修改呢，修改一个节点，必须修改其所有祖先，最坏情况下为修改第一个元素，最多有log(n)的祖先。

树状数组维护区间最值模板1. 什么是树状数组？树状数组（Fenwick Tree），也称为二进制索引树（Binary Indexed Tree，BIT），是一种用于高效计算前缀和、区间和以及维护区间最值的数据结构。

它可以在O(logn)的时间复杂度内完成单点更新和查询操作。

2. 树状数组的原理树状数组的核心思想是利用二进制位的特性来进行高效计算。

它将原始序列分解为多个子序列，并利用每个子序列的前缀和来表示该子序列中元素的累加和。

具体地，设原始序列为a[1…n]，树状数组C[1…n]用于存储每个子序列的前缀和。

其中，C[i]表示以a[i]为末尾元素的子序列的累加和。

对于某个位置i，其对应的父节点位置可以通过将i的二进制表示中最低位1变为0来计算得到。

例如，对于二进制表示为1010（十进制为10）的位置i，其父节点位置为1000（十进制为8）。

树状数组支持两种操作：单点更新和区间查询。

•单点更新：当某个位置i发生变化时，需要更新其对应的所有父节点位置的值。

具体操作为将i的二进制表示中最低位1变为0，并依次向上更新。

•区间查询：要求计算区间[l, r]的和（或最值），可以通过计算C[r] - C[l-1]得到。

其中，C[r]表示以a[r]为末尾元素的子序列的累加和，C[l-1]表示以a[l-1]为末尾元素的子序列的累加和。

这样计算得到的差值即为区间[l, r]内元素的累加和。

3. 树状数组维护区间最值模板树状数组不仅可以用于维护前缀和，还可以用于维护区间最值。

以下是树状数组维护区间最值的模板代码：const int MAXN = 100000; // 树状数组大小int a[MAXN]; // 原始序列int C[MAXN]; // 树状数组// 单点更新操作void update(int pos, int val) {while (pos <= MAXN) {C[pos] = max(C[pos], val); // 维护区间最大值，如果是求和则改为C[pos]+= valpos += lowbit(pos); // 计算下一个父节点位置}}// 区间查询操作int query(int pos) {int res = 0;while (pos > 0) {res = max(res, C[pos]); // 维护区间最大值，如果是求和则改为res+=C[pos] pos -= lowbit(pos); // 计算下一个查询位置}return res;}// 计算pos的二进制表示中最低位1所对应的值int lowbit(int pos) {return pos & -pos;}4. 树状数组维护区间最值模板的使用示例以下是一个使用树状数组维护区间最值模板的示例，用于求解原始序列中某个区间内的最大值：#include <iostream>using namespace std;const int MAXN = 100000; // 树状数组大小int a[MAXN]; // 原始序列int C[MAXN]; // 树状数组// 单点更新操作void update(int pos, int val) {while (pos <= MAXN) {C[pos] = max(C[pos], val);pos += lowbit(pos);}}// 区间查询操作int query(int pos) {int res = 0;while (pos > 0) {res = max(res, C[pos]);pos -= lowbit(pos);}return res;}// 计算pos的二进制表示中最低位1所对应的值int lowbit(int pos) {return pos & -pos;}int main() {int n; // 序列长度cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];update(i, a[i]);}int q; // 查询次数cin >> q;while (q--) {int l, r; // 查询区间cin >> l >> r;int max_val = query(r) - query(l-1);cout << "区间最大值：" << max_val << endl;}return 0;}5. 总结树状数组是一种高效的数据结构，适用于解决多种问题，包括维护前缀和、区间和以及维护区间最值等。

树状数组求区间和的一些常见模型树状数组在区间求和问题上有大用，其三种复杂度都比线段树要低很多……有关区间求和的问题主要有以下三个模型（以下设A[1..N]为一个长为N的序列，初始值为全0）：（1）“改点求段”型，即对于序列A有以下操作：【1】修改操作：将A[x]的值加上c；【2】求和操作：求此时A[l..r]的和。

这是最容易的模型，不需要任何辅助数组。

树状数组中从x开始不断减lowbit(x)（即x&(-x)）可以得到整个[1..x]的和，而从x开始不断加lowbit(x)则可以得到x的所有前趋。

代码：操作【1】：ADD(x, c);操作【2】：SUM(r)-SUM(l-1)。

（2）“改段求点”型，即对于序列A有以下操作：【1】修改操作：将A[l..r]之间的全部元素值加上c；【2】求和操作：求此时A[x]的值。

这个模型中需要设置一个辅助数组B：B[i]表示A[1..i]到目前为止共被整体加了多少（或者可以说成，到目前为止的所有ADD(i, c)操作中c的总和）。

则可以发现，对于之前的所有ADD(x, c)操作，当且仅当x>=i时，该操作会对A[i]的值造成影响（将A[i]加上c），又由于初始A[i]=0，所以有A[i] = B[i..N]之和！而ADD(i, c)（将A[1..i]整体加上c），将B[i]加上c即可——只要对B数组进行操作就行了。

这样就把该模型转化成了“改点求段”型，只是有一点不同的是，SUM(x)不是求B[1..x]的和而是求B[x..N]的和，此时只需把ADD和SUM中的增减次序对调即可（模型1中是操作【1】：ADD(l-1, -c); ADD(r, c);操作【2】：SUM(x)。

（3）“改段求段”型，即对于序列A有以下操作：【1】修改操作：将A[l..r]之间的全部元素值加上c；【2】求和操作：求此时A[l..r]的和。

这是最复杂的模型，需要两个辅助数组：B[i]表示A[1..i]到目前为止共被整体加了多少（和模型2中的一样），C[i]表示A[1..i]到目前为止共被整体加了多少的总和（或者说，C[i]=B[i]*i）。