线段树（指针板子）

指针线段树：

指针写其实和普通的思路上没啥区别；

1.把树封装到结构体里；

2.在树里每个节点的信息也放结构体里，

3.像 mid， len 之类的可以在节点里写函数也可以宏定义

4.只需存一个根节点的指针（不用考虑数组开多大）， 其他节点的指针都在父节点里存着；

5.构造函数要给指针附上NULL

6.注意建树时加上取地址， 动态开点的话， chenge函数要取地址；

7.然后就疯狂指就醒了

没打算写神魔详解之类的， 毕竟是个板子

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <iostream>
#define N 1000005
#define int long long
#define qwq  cout<<"!!!!!"<<endl;
using namespace std;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f*x;
}
int n,m,a[N];
struct Segment
{
    struct node 
    {
        int l, r, sum, add;
        node *L, *R;
        node(int l, int r) : l(l), r(r), sum(0), add(0), L(NULL), R(NULL) {}
        
        int mid(){return (l + r)>>1; }
        int len(){return (r - l + 1); }
        void up() {
            sum = (L->sum + R->sum);
        }
        void down() {
            L->sum += (add *(L->len()) );
            R->sum += (add *(R->len()) );
            L->add += add;
            R->add += add;
            add = 0;
        }
        
    }*root;
    
    void build(node *&k, int l, int r)
    {
        k =new node(l, r);
        if(l == r)  {
            k->sum = a[l];
            return ;
        }
        build(k->L, k->l, k->mid());
        build(k->R, k->mid()+1, r);
        k->up();
    }
    
    void chenge(node *k, int l, int r, int val)
    {
        if(l<= k->l&&r>= k->r) {
            k->sum += val*(k->len());
            k->add += val;
            return ;
        }
        if(k->add) k->down();
        if(l <= k->mid())chenge(k->L, l, r, val);
        if(r >= k->mid() +1 )chenge(k->R, l, r, val);
        k->up();
    }
    
    int ask(node *k, int l, int r)
    {
        if(l<= k->l && r >= k->r)
            return k->sum;
        if(k->add)k->down();
        int res = 0;
        if(l <= k->mid()) res += ask(k->L, l, r);
        if(r >= k->mid() + 1) res += ask(k->R, l, r);
        return res;
    }
}A;
signed main()
{
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    n = read();m = read();
    for(int i = 1; i <= n; i ++)
        a[i] =read();
    A.build(A.root, 1 , n);
    for(int i = 1; i <= m; i ++)
     {
        int opt, x, y, z;
        opt = read();
        if(opt == 1 )   {
            x=read();y=read(); z=read();
            A.chenge(A.root, x, y, z);
        }
        else    {
            x=read(); y = read();
            cout << A.ask(A.root, x, y)<<endl;
        }
         
     }
    return 0;
}

线段树（指针板子）

原文：https://www.cnblogs.com/spbv587/p/11656703.html