Tree arrays are data structures that solve dynamic prefixes and problems. Larks always associate ST tables, tree arrays, and segment trees, which are all methods to solve dynamic interval problems.
A tree array is a secondorder prefix and array of two. Like a tree, as shown in the diagram, the prefix and length of each location I are lowbit(i), and the interval length between depths is lowbit(i), for example, to t[4] +1, the t[8] containing t[4] is followed by a + 1.
So when we ask for the prefix sum of 6, because it should be the interval that 6 contains plus the interval that precedes the interval that 6 contains, that is, t[4] + t[6].
If the intervals and times of 3 to 6 are prefix and 6prefix and 2, while prefix and 6 = t[6] + t[4], so the sum of the intervals of 3 to 6 is t[6] + t[4]  t[2].
Single point addition:
//Father's position with a dot must be added with b void add(int a,int b){ for(int i=a;i<=n;i+=lowbit(i)) t[i]+=b; }
Prefix and:
//The sum of the intervals x contains and before the + X interval //The length of the xinterval is lowbit(x) int sum(int x){ int ans=0; for(int i=x;i>0;i=lowbit(i)) ans+=t[i]; return ans; }
Here are the singlepoint value changes and interval and query questions
P3374 [Template] Tree Array 1  Logus  New Ecology for Computer Science Education (luogu.com.cn)
Title Description
If you know a sequence, you need to do two things:

Add a number to x

Find the sum of every number in an interval
Input Format
The first row contains two positive integers, N and m, representing the number of numbers in the column and the total number of operations.
The second row contains n spacedelimited integers, where the number i represents the initial value of item i of the column.
Next, m lines contain 3 integers per line, representing an operation as follows:

1 x k Meaning: Add x to K

2 x y Meaning: Sum of each number in the output interval [x,y]
This makes the question obvious
The return value of lowbit(x) is x binary minimum bit 1, so it returns x &x, which I define with a macro
#include <bits/stdc++.h> #define rep(i,n,m) for(int i=n;i<=m;++i) #define per(i,n,m) for(int i=n;i>=m;i) #define PII pair<int,int> #define lowbit(x) x&x #define INF 1<<30 using namespace std; typedef long long ll; const int N=5e5+10; int t[N],n,q; void add(int a,int b){ //Father Node+b for(int i=a;i<=n;i+=lowbit(i))t[i]+=b; } int sum(int x){ int ans=0; Each previous interval sum for(int i=x;i>0;i=lowbit(i))ans+=t[i]; return ans; } int main() { ios::sync_with_stdio(0);cin.tie(0); cin>>n>>q; rep(i,1,n){ int x;cin>>x; add(i,x); } while(q){ int a,b,c;cin>>a>>b>>c; if(a==1) add(b,c); else cout<<sum(c)sum(b1)<<endl; //Prefixes and Differences } return 0; }
There are also interval change values and singlepoint queries.
P3368 [Template] Tree Array 2  Logus  New Ecology for Computer Science Education (luogu.com.cn)
Title Description
If you know a sequence, you need to do two things:

Add x to each number in an interval;

Find the value of a number.
Input Format
The first row contains two integers, N and M, representing the number of numbers in the column and the total number of operations.
The second row contains N spacedelimited integers, where the number i represents the initial value of item i of the column.
Next, the M line contains 22 or 44 integers each, representing an operation as follows:
Operation 1: Format: 1 x y k Meaning: Add K to each number in the interval [x,y];
Operation 2: Format: 2 x Meaning: Output the value of number X.
subscript i 0 1 2 3 4 5 6 7 Original Value a 0 1 2 1 2 4 9 0 differential value b 0 1 1 1 3 6 5 9
For the sum of the intervals after changing the values of the intervals, we know that the difference can be used. What is the difference?
The difference b[i] is a[i]  a[i1], and a[n] can be usedRepresents (Hahaha, big formula). When the interval [l, r] is + x, only b[l] +x, b[r+1] x is needed to guarantee that only the value in the interval increases
For this problem, we might initialize the difference array to be 0, then change the secondary interval value to operate on the difference array boundary twice.
The final singlepoint query is the altered difference plus the original value, sum(x) + a[x]
(The difference array is represented by the tarray and the original number array by the qarray below)
#include <bits/stdc++.h> #define rep(i,n,m) for(int i=n;i<=m;++i) #define per(i,n,m) for(int i=n;i>=m;i) #define PII pair<int,int> #define lowbit(x) x&x #define INF 1<<30 using namespace std; typedef long long ll; const int N=5e5+10; int q[N],t[N],n,T; void add(int a,int b){ for(int i=a;i<=n;i+=lowbit(i))t[i]+=b; } int sum(int x){ int ans=0; for(int i=x;i>0;i=lowbit(i))ans+=t[i]; return ans; } int main() { ios::sync_with_stdio(0);cin.tie(0); cin>>n>>T; rep(i,1,n)cin>>q[i]; while(T){ int x,a,b,c;cin>>x; if(x==1){ cin>>a>>b>>c; //Differential Boundary Operation add(a,c); add(b+1,c); }else { cin>>a; //SinglePoint Query Value=Differential Array Prefix and+Original Value cout<<sum(a)+q[a]<<endl; } } return 0; }
For some examples that cross the boundary, change int to long if necessary.
Today, I just learned and swallowed dates a little. The description is not clear.