指针线段树:
指针写其实和普通的思路上没啥区别;
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;
}