Getting started with tree arrays

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 second-order 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 6-prefix 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 x-interval 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 single-point 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 space-delimited 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(b-1)<<endl;
            //Prefixes and Differences
    }
    return 0;
}

There are also interval change values and single-point 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:

  1. Add x to each number in an interval;

  2. 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 space-delimited 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[i-1], 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 single-point query is the altered difference plus the original value, sum(x) + a[x]

(The difference array is represented by the t-array and the original number array by the q-array 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;
            //Single-Point 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.

Tags: data structure

Posted by cityguru on Wed, 17 Aug 2022 22:30:29 +0300