IndexTree可以以O(logN)的时间得到任意前缀和，并同时支持在O(logN)时间内支持动态单点值的修改。空间复杂度O(N)。
相比于线段树对一段区间进行修改，IndexTree适合对数组的单点进行修改。因为线段树如果进行单点修改，那么它大量的非叶子节点都要进行修改。
不同于一般的前缀和数组，IndexTree前缀和数组0位置抛弃不用。
IndexTree前缀和数组第 i 位置，将i转化成二进制，将最后边的1削掉，然后加1，假设得到的数是x，原数组中x~i的和就是第 i 位置所填的值。
假设 i 为8，它的二进制序列为1000，我们将它最右边的1消掉再将这个数加1：也就是0000+1=0001，他前缀和的范围就是消去最右边1的数+1到他本身也就是1~8，也就是说原数组第1个数到第8个数的累加和放到IndexTree的前缀和数组第8个位置。
比如求1~33的累加和，33的二进制为100001，那它的累加和就是它本身加上累加和数组中第32（100000）个位置，因为第32个位置的前缀和就是原数组中0~100000位置的和。
#include<vector>
#include<queue>
#include<string>
#include<iostream>
using namespace std;
class IndexTree {
public:
//下标从1开始
IndexTree(int size)
:tree(size + 1)
, n(size)
{}
//从1~index的累加和
long long sum(int index)
{
long long ret = 0;
while (index > 0)
{
//index&-index:提取index最右侧的1来
//
//比如我们要求1~12位置的累加和
//12的二进制位1100，先加上tree[1100]
//因为tree[1100]的位置是1001~1100的累加和
//再将最右端的1去掉，加上tree[1000]
//tree[1000]的位置是1~1000的累加和
ret += tree[index];
index -= (index & -index);
}
return ret;
}
void add(int index, int d)
{
//index&-index:提取index最右侧的1来
//给index位置加上d，那么其他位置也会受到影响
//
//比如给1位置加上d，
// 2位置是1~2的和，8位置是1~8的和，4位置是1~4的和
//这些位置都得加上d
while (index <= n)
{
tree[index] += d;
index += (index & -index);
}
}
//求从原数组中index1~index2的和
long long RangeSum(int index1, int index2)
{
return sum(index2) - sum(index1);
}
private:
vector<long long>tree;
int n;
};
int main()
{
int n=0,q=0;
cin>>n>>q;
vector<long long>v(n);
IndexTree indexTree(n);
for(int i=0;i<n;i++)
{
cin>>v[i];
indexTree.add(i+1,v[i]);
}
while(q--)
{
int index1,index2;
cin>>index1>>index2;
cout<<indexTree.RangeSum(index1-1,index2)<<endl;
}
}
indexTree相比线段树的优点就是indexTree改成二维的非常的容易的改。indexTree在二维中同样的第一行和第一列的位置是空出来不使用的，这与一维的类似，而在二维中求累加和和一维的原理一样，只不过是多了列。更新也是一样的原理只不过比一维的多了列。
817 · 范围矩阵元素和-可变的
class NumMatrix {
public:
vector<vector<int>>tree;
vector<vector<int>>nums;
int N;
int M;
NumMatrix(vector<vector<int>> matrix)
{
if(matrix.size()==0||matrix[0].size()==0)
{
return;
}
N=matrix.size();
M=matrix[0].size();
tree.resize(N+1,vector<int>(M+1));
nums.resize(N,vector<int>(M));
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
update(i,j,matrix[i][j]);
}
}
}
//从(1,1)到(row,col)的累加和
int sum(int row,int col)
{
int res=0;
for(int i=row+1;i>0;i-=i&(-i))
{
for(int j=col+1;j>0;j-=j&(-j))
{
res+=tree[i][j];
}
}
return res;
}
void update(int row, int col, int val) {
if(N==0||M==0)
{
return;
}
int add=val-nums[row][col];
nums[row][col]=val;
for(int i=row+1;i<=N;i+=i&(-i))
{
for(int j=col+1;j<=M;j+=j&(-j))
{
tree[i][j]+=add;
}
}
}
int sumRegion(int row1, int col1, int row2, int col2)
{
if(N==0||M==0)
{
return 0;
}
return sum(row2,col2)+sum(row1-1,col1-1)-sum(row1-1,col2)-sum(row2,col1-1);
}
};