Tree array

Preface

Tree array _ Baidu Encyclopedia

Speaking of tree structure , The biggest advantage is that it can make $O(n)$ Some operations of are simplified to $O(logn)$

And the theme of this article “ Tree array ” Nature is no exception

The tree array is used in binary 1 The number and relationship of , Let large numbers hold decimal values .

But because the halo of the segment tree is too big , The discussion of tree array is too low , But it's still necessary to know

This question does not follow 0 Start to explain , Mainly the display and use of templates

Be careful ： The subscript of the tree array is from 1 At the beginning （1~n）

Related explanations

Area and retrieval - Array can be modified - Try to answer the official questions

〔manim | Algorithm | data structure 〕 Fully understand and apply tree arrays | Support multiple dynamic maintenance interval operations

lowbit()

Explain ：2 The power of - Try to answer the official questions

It is actually difficult to find the law directly

From the point of view of adjacent large numbers and decimals, the close relationship lies in the 1 The difference between , So we need to quickly get the end of 1

Need lowbit() function , The specific principle can be understood by self simulation ( Basic knowledge of bit operation )

Exercises

Luogu ：P3374 【 Templates 】 Tree array 1 Single point modification , Interval query

Luogu ：P3368 【 Templates 】 Tree array 2 Interval modification , Single point query

Hang Dian ： The enemy troops were arrayed - 1166

Hang Dian ：Color the ball 1556

Power button ：307. Area and retrieval - Array can be modified

Power button ：315. Count the number of elements on the right less than the current one

Power button ：2179. Count the number of good triples in the array

Classical problems ：( Total number of pairs in reverse order ) discretization + Tree array

Power button ： The finger of the sword Offer 51. Reverse pairs in arrays

Implementation and application

Core function

//  Subscript  [1, n]
class TreeArray {
    
private:
    int n;
    vector<int> tree;

    inline int lowbit(int x) {
     return x & (-x); }

public:
    TreeArray() {
    }
    TreeArray(int n) : n(n), tree(n + 1) {
    }

    void add(int i, int val) {
    
        for (; i <= n; i += lowbit(i)) {
    
            tree[i] += val;
        }
    }

    int ask(int i) {
    
        int sum = 0;
        for (; i > 0; i -= lowbit(i)) {
    
            sum += tree[i];
        }
        return sum;
    }
};

Extended application

//  Single point modification , Query prefix and 
add(x, val);
ans = ask(x);

//  Single point modification , Single point query 
add(x, val);
ans = ask(x) - ask(x - 1);

//  Single point modification , Interval query 
add(x, val);
ans = ask(r) - ask(l - 1);  // Right -（ Left -1）
/** ************************************************************/
//  Interval modification , Single point query  （ Here we use a differential array ）
add(l, val);
add(r + 1, -val);
ans = arr[x] + ask(x);	// arr Represents raw data ,ask The difference is recorded 
/** ************************************************************/
//  Interval modification , Interval query 
//  The code is longer than the , See the example below directly 

---

The sample code

Single point modification Interval query

// P3374 【 Templates 】 Tree array  1
#include <bits/stdc++.h>
using namespace std;

class TreeArray {
    
private:
    int n;
    vector<int> tree;

public:
    TreeArray() {
    }
    TreeArray(int n) : n(n), tree(n + 1) {
    }

    inline int lowbit(int x) {
     return x & (-x); }

    void add(int i, int val) {
    
        for (; i <= n; i += lowbit(i)) {
    
            tree[i] += val;
        }
    }

    int ask(int i) {
    
        int sum = 0;
        for (; i > 0; i -= lowbit(i)) {
    
            sum += tree[i];
        }
        return sum;
    }
};

int main() {
    
    int n, m;
    cin >> n >> m;

    TreeArray tarr(n);

    for (int i = 1, val; i <= n; i++) {
    
        cin >> val;
        tarr.add(i, val);
    }

    while (m--) {
    
        int inquire;
        cin >> inquire;

        if (inquire == 1) {
    
            int pos, val;
            cin >> pos >> val;
            tarr.add(pos, val);
        } else {
    
            int left, right;
            cin >> left >> right;
            int ans = tarr.ask(right) - tarr.ask(left - 1);
            cout << ans << endl;
        }
    }

    return 0;
}

Interval modification Single point query

// P3368 【 Templates 】 Tree array  2
//  The tree array stores changing values 
#include <bits/stdc++.h>
using namespace std;

class TreeArray {
    
private:
    int n;
    vector<int> arr;   //  Store raw data values 
    vector<int> tree;  //  Store the difference value 

public:
    TreeArray() {
    }
    TreeArray(int n) : n(n), tree(n + 1) {
    }
    TreeArray(int n, vector<int>& arr) : n(n), tree(n + 1), arr(arr) {
    }

    inline int lowbit(int x) {
     return x & (-x); }

    void add(int i, int val) {
    
        for (; i <= n; i += lowbit(i)) {
    
            tree[i] += val;
        }
    }

    int ask(int i) {
    
        int sum = 0;
        for (; i > 0; i -= lowbit(i)) {
    
            sum += tree[i];
        }
        return sum;
    }

    int query(int i) {
     
        return arr[i] + ask(i);
    }
};

int main() {
    
    int n, m;
    cin >> n >> m;

    vector<int> arr(n + 1);
    for (int i = 1; i <= n; i++) {
    
        cin >> arr[i];
    }

    TreeArray tarr(n, arr);

    while (m--) {
    
        int inquire;
        cin >> inquire;

        if (inquire == 1) {
    
            int left, right, val;
            cin >> left >> right >> val;
            tarr.add(left, val);        //  Left  +
            tarr.add(right + 1, -val);  //  Right +1 -
        } else {
    
            int x;
            cin >> x;
            cout << tarr.query(x) << endl;
        }
    }

    return 0;
}

Interval modification Interval query

You need to define two arrays , It is derived mathematically , It's hard to understand just looking at words , Just memorize

Exercises ：

Luogu ：P3384 【 Templates 】 Heavy chain subdivision / The tree chain splits

Because I didn't find a suitable simple problem, I used this problem , To complete this problem, you need to be able to dissect the tree chain

But this article focuses on the following tool template classes TreeArray The implementation and call of

---

The general flow of this question ：

• The recursive sequence is obtained by tree chain partition idx[] Subscript and newVal[] Corresponding point weight
• Initialize the tree array with the new point weight ( Manual cycle initialization )
• Using tree chain partition lca operation , Query and update
• Be careful ： Because there will be subtraction and negative numbers , Pay attention to when taking mold

// P3384 【 Templates 】 Heavy chain subdivision / The tree chain splits 
//  The tree chain splits  +  Tree array  ( Line segment tree is OK )
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int M = 10 + 1 * 100000;
static int mod = 1e9 + 7;  //  Random assignment , The title requires manual input 
/** ******************************************************************/

vector<int> oldVal(M);  //  Initial value of point weight 
vector<int> newVal(M);  //  The corresponding value after sectioning 
/** ******************************************************************/

//  Tree array 
//  Interval modification   Interval query 
class TreeArray {
    
private:
    int n;
    vector<int> tree1;
    vector<int> tree2;

    inline int lowbit(int x) {
     return x & (-x); }

    void updata(int i, int val) {
    
        for (int p = i; i <= n; i += lowbit(i)) {
    
            tree1[i] += val;
            tree2[i] += p * val;
            //  Note the negative modulus 
            tree1[i] %= mod;    tree1[i] = (tree1[i] + mod) % mod;
            tree2[i] %= mod;    tree2[i] = (tree2[i] + mod) % mod;
        }
    }

    int query(int i) {
    
        int sum = 0;
        for (int p = i; i > 0; i -= lowbit(i)) {
    
            sum += (p + 1) * tree1[i] - tree2[i];
            sum %= mod;     sum = (sum + mod) % mod;
        }
        return sum;
    }

public:
    TreeArray() {
    }
    TreeArray(int n) : n(n), tree1(n + 1), tree2(n + 1) {
    }

    //  Interval modification 
    void rangeUpdata(int left, int right, int val) {
    
        updata(left, val);
        updata(right + 1, -val);
    }
    //  Interval query 
    int rangeQuery(int left, int right) {
    
        return (query(right) - query(left - 1) + mod) % mod;
    }
};

TreeArray tarr;  //  Global object , Easy lca call 
/** ******************************************************************/

//  Tree chain split template 
vector<vector<int>> graph(M);  //  chart 
vector<int> father(M);         //  Parent node 
vector<int> son(M);            //  Heavy child 
vector<int> size(M);           //  The number of subtree nodes 
vector<int> deep(M);           //  depth , The root node is 1
vector<int> top(M);            //  The head of the heavy chain , Ancestors 
vector<int> idx(M);            //  Split new idx
int cnt = 0;                   //  Split count 

void dfs1(int cur, int from) {
    
    deep[cur] = deep[from] + 1;  //  depth , Never change to 
    father[cur] = from;          //  Parent node , Record to 
    size[cur] = 1;               //  The number of nodes in the subtree 
    son[cur] = 0;                //  Heavy child  ( Default to 0 It means nothing )
    for (int& to : graph[cur]) {
    
        if (to == from) {
      //  Avoid the loop 
            continue;
        }
        dfs1(to, cur);                    //  Processing child nodes 
        size[cur] += size[to];            //  The number of nodes is superimposed 
        if (size[son[cur]] < size[to]) {
      //  Slack operation , Update heavy child 
            son[cur] = to;
        }
    }
}

void dfs2(int cur, int grandfather) {
    
    top[cur] = grandfather;     // top Record ancestors 
    idx[cur] = ++cnt;           //  Record the sectioning idx
    newVal[cnt] = oldVal[cur];  //  Map to new value 
    if (son[cur] != 0) {
            //  first dfs Heavy son 
        dfs2(son[cur], grandfather);
    }
    for (int& to : graph[cur]) {
    
        if (to == father[cur] || to == son[cur]) {
    
            continue;  //  No cur Parent node , It's not about kids 
        }
        dfs2(to, to);  // dfs Light child 
    }
}
// lca Templates   Not used in this question 
int lca(int x, int y) {
    
    while (top[x] != top[y]) {
      //  until top Ancestors want to wait 
        if (deep[top[x]] < deep[top[y]]) {
    
            swap(x, y);  //  Compare top The depth of ancestry ,x Always set to deeper 
        }
        x = father[top[x]];  //  Jump straight to top Parent node 
    }
    return deep[x] < deep[y] ? x : y;  //  In the same heavy chain , The deeper ones are the ancestors 
}
/** ******************************************************************/

void updatePath(int x, int y, int val) {
    
    while (top[x] != top[y]) {
    
        if (deep[top[x]] < deep[top[y]]) {
    
            swap(x, y);
        }
        tarr.rangeUpdata(idx[top[x]], idx[x], val);
        x = father[top[x]];
    }
    if (deep[x] < deep[y]) {
    
        swap(x, y);
    }
    tarr.rangeUpdata(idx[y], idx[x], val);
}

void updateTree(int root, int val) {
    
    tarr.rangeUpdata(idx[root], idx[root] + size[root] - 1, val);
}

int queryPath(int x, int y) {
    
    int sum = 0;
    while (top[x] != top[y]) {
    
        if (deep[top[x]] < deep[top[y]]) {
    
            swap(x, y);
        }
        sum += tarr.rangeQuery(idx[top[x]], idx[x]);
        sum %= mod;
        x = father[top[x]];
    }
    if (deep[x] < deep[y]) {
    
        swap(x, y);
    }
    sum += tarr.rangeQuery(idx[y], idx[x]);
    return sum % mod;
}

int queryTree(int root) {
    
    return tarr.rangeQuery(idx[root], idx[root] + size[root] - 1);
}
/** ******************************************************************/

signed main() {
    
    int n, m, root;
    cin >> n >> m >> root >> mod;

    for (int i = 1; i <= n; i++) {
    
        cin >> oldVal[i];
    }

    //  The tree number  [1, n]
    //  This topic only says that there is an edge , No direction 
    for (int i = 1, u, v; i <= n - 1; i++) {
    
        cin >> u >> v;
        graph[v].emplace_back(u);
        graph[u].emplace_back(v);
    }

    //  The tree chain splits   heavy chain 
    dfs1(root, 0);
    dfs2(root, root);
    //  According to the mapped newVal Build up trees 
    tarr = TreeArray(n);
    //  Interval modification   Interval query   Manual initialization is required 
    for (int i = 1; i <= n; i++) {
    
        tarr.rangeUpdata(i, i, newVal[i]);
    }

    for (int i = 1, ask; i <= m; i++) {
    
        cin >> ask;
        int from, to, val, subtree;
        if (ask == 1) {
    
            cin >> from >> to >> val;
            updatePath(from, to, val);
        } else if (ask == 2) {
    
            cin >> from >> to;
            cout << queryPath(from, to) % mod << endl;
        } else if (ask == 3) {
    
            cin >> subtree >> val;
            updateTree(subtree, val);
        } else {
    
            cin >> subtree;
            cout << queryTree(subtree) % mod << endl;
        }
    }

    return 0;
}

Classic application Total number of pairs in reverse order

Power button ： The finger of the sword Offer 51. Reverse pairs in arrays

discretization ：( Simplify complexity ) discretization _ Tianci Xilian's blog -CSDN Blog _ Discrete time complexity

The discretization written in the official solution is much simpler

//  Subscript  [1, n]
class TreeArray {
    
private:
    int n;
    vector<int> tree;

    inline int lowbit(int x) {
     return x & (-x); }

public:
    TreeArray() {
    }
    TreeArray(int n) : n(n), tree(n + 1) {
    }

    void add(int i, int val) {
    
        for (; i <= n; i += lowbit(i)) {
    
            tree[i] += val;
        }
    }

    int ask(int i) {
    
        int sum = 0;
        for (; i > 0; i -= lowbit(i)) {
    
            sum += tree[i];
        }
        return sum;
    }
};

class Solution {
    
public:
    int reversePairs(vector<int>& nums) {
    
        int n = nums.size();
        if (n < 2) {
    
            return 0;
        }
        //  Get the discretized array 
        vector<int> arr = toDiscretization(nums);

        TreeArray ta(n);

        int ans = 0;
        for (int i = 0; i < n; i++) {
    
            int cur = arr[i];
            //  Sum from recorded values larger than the current value , But it cannot include itself 
            ans += ta.ask(n) - ta.ask(cur);
            //  Add tree array , Serve for subsequent operations 
            ta.add(cur, 1);
        }

        return ans;
    }

private:
    //  The same value needs to be considered , Consider a tree array that specifies subscripts from 1 Start 
    vector<int> toDiscretization(vector<int>& arr, int idx = 1) {
    
        int n = arr.size();
        if (n == 0) {
    
            return {
    };
        }
        multimap<int, int> mmp;
        for (int i = 0; i < n; i++) {
    
            mmp.insert({
    arr[i], i});
        }

        vector<int> discretization(n);
        auto it = mmp.begin();
        int pre = it->first;
        discretization[it->second] = idx;
        for (it++; it != mmp.end(); it++) {
    
            int cur = it->first;
            int i = it->second;
            if (cur == pre) {
    
                discretization[i] = idx;
            } else {
    
                discretization[i] = (++idx);
            }
            pre = cur;
        }

        return discretization;
    }
};

---

---

---

END