Based on Zeng Shen's explanation, the line segment tree is studied again one

Concept

A line tree is a binary tree , That is, for a line segment , We will use a binary tree to represent . For example, a length of 4 The line segment , We can express it like this ：

  Also, the length is n

（ Ugly ）

Generalization ： node i A weight = Her left son + Her right son . because 1-4 The sum of is equal to 1-2 And 2-3 And

According to this idea , Then we can make achievements , Let's set up a structure tree,tree[i].l and tree[i].r Respectively represent the left and right subscripts of the line segment represented by this point ,tree[i].sum Represents the line segment and... Represented by this node .

We know , A binary tree , Her left and right sons are numbered her respectively *2 And her *2+1

According to the nature just now , Get the formula ：t r e e [ i ] . s u m = t r e e [ i ∗ 2 ] . s u m + t r e e [ i ∗ 2 + 1 ] . s u m ; tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;tree[i].sum=tree[i∗2].sum+tree[i∗2+1].sum; You can build a segment tree ！

The code is as follows ：

inline void build(int i,int l,int r){// Recursive tree building 
    tree[i].l=l;tree[i].r=r;
    if(l==r){// If this node is a leaf node 
        tree[i].sum=input[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(i*2,l,mid);// Construct left subtree and right subtree respectively 
    build(i*2+1,mid+1,r);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;// The properties we just found return ;
}