Indextree and Application

---

IndexTree

IndexTree We can use O(logN) The time to get any prefix and , And support in O(logN) Dynamic single point value modification is supported in time . Spatial complexity O(N).
Compared with the segment tree, a segment is modified ,IndexTree It is suitable for modifying the single point of the array . Because if the segment tree is modified at a single point , Then a large number of non leaf nodes have to be modified .

IndexTree Prefix and array

Different from common prefixes and arrays ,IndexTree Prefixes and arrays 0 The position is abandoned .
IndexTree Prefix and array number i Location , take i Convert to binary , Put the last 1 Cut off , Then add 1, Suppose the number is x, In the original array x~i The sum of is the second i The value filled in the position .

hypothesis i by 8, Its binary sequence is 1000, We put it on the far right 1 Eliminate and add this number 1： That is to say 0000+1=0001, The range of his prefix and is to eliminate the rightmost 1 Number of numbers +1 To himself is 1~8, That is to say, the original array is 1 The number to the first 8 The sum of the numbers is added to IndexTree Prefix of and array number 8 A place .

For example, please 1~33 Summation of ,33 The binary of is 100001, Then its cumulative sum is itself plus the cumulative sum in the array 32（100000） A place , Because the first 32 The sum of the prefixes of the positions is in the original array 0~100000 Position and .

Code implementation

DP34 【 Templates 】 The prefix and

#include<vector>
#include<queue>
#include<string>
#include<iostream>
using namespace std;

class IndexTree {
    
public:
	// Subscript from 1 Start 
	IndexTree(int size)
		:tree(size + 1)
		, n(size)
	{
    }
	// from 1~index Summation of 
	long long sum(int index) 
	{
    

		long long ret = 0;
		while (index > 0) 
		{
    
			//index&-index: extract index The most the right side 1 Come on 
			// 
			// For example, we ask 1~12 The cumulative sum of positions 
			//12 Binary bit of 1100, First plus tree[1100]
			// because tree[1100] The position is 1001~1100 Summation of 
			// And then put the rightmost 1 Get rid of , add tree[1000]
			//tree[1000] The position is 1~1000 Summation of 
			ret += tree[index];
			index -= (index & -index);
		}
		return ret;
	}
	void add(int index, int d) 
	{
    
		//index&-index: extract index The most the right side 1 Come on 
		// to index Position plus d, Then other locations will also be affected 
		// 
		// Such as to 1 Position plus d,
		// 2 Location is 1~2 And ,8 Location is 1~8 And ,4 Location is 1~4 And 
		// These positions have to be added d
		while (index <= n) 
		{
    
			tree[index] += d;
			index += (index & -index);
		}
	}
	// From the original array index1~index2 And 
	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;
    }
}

A two-dimensional IndexTree

indexTree The advantage over the segment tree is indexTree It is very easy to change to two-dimensional .indexTree In two dimensions, the same position of the first row and the first column is empty , This is similar to one dimension , The principle of accumulation in two dimensions is the same as that in one dimension , It's just that there are more columns . The same principle applies to updates, except that there are more columns than one-dimensional ones .
817 · Range matrix elements and - Variable

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]);
            }
        }
    }
    // from (1,1) To (row,col) Summation of 
    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);
    }
};