一些有趣的线段树push-ups

1

题目

nn个数a1na_{1\cdots n}排成一列,支持两种操作:
1 x y kaxya_{x\cdots y}加上kk
2 x y 查询i=xyai2\sum_{i=x}^{y}a_i^2

n,q1×105n, q\leq1\times10^5

操作

维护区间和,区间平方和。

如果把axya_{x\cdots y}中的每一个数加上kk的话,sum(x,y)=sum(x,y)+k×(yx+1)sum(x,y)'=sum(x,y)+k\times(y-x+1)sum2(x,y)=sum2(x,y)+2sum(x,y)+(yx+1)k2sum^2(x,y)'=sum^2(x,y)+2sum(x,y)'+(y-x+1)k^2

阅读更多

线段树的动态开点

动态开点解决的问题

n1×109n\leq1\times10^9,建树直接爆00

动态开点的要点:

  • 第一次访问到某一个节点的时候,建立这个节点。
  • 对于树上的每一个节点,存储其左子树和右子树根节点的编号。
阅读更多

ymoi集训-线段树

线段树基本概念略。

以下代码中一些宏定义如下:

1
2
3
4
5
6
7
#define mid ((l+r)>>1)
#define lc (o<<1)
#define rc (o<<1|1)
#define lcq lc,l,mid
#define rcq rc,mid+1,r
#define oq o,l,r
#define od int o,int l,int r
阅读更多
Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×