当前位置: 首页 > news >正文

数据结构--zkw线段树

好几天没写了,写点儿奇怪的东西,一个不好理解的黑科技。


zkw线段树,顾名思义,就是zkw大神发明的线段树。
由于我实在是太弱了,无法讲述zkw大神的高深的ppt,就留一个下载网址:统计的力量(zkw线段树)
我这里要说的,就是zkw线段树的具体用法,首先,原版zkw只能做到单点修改&区间查询,可是这并无卵用,因为树状数组完全可以替代它。
但是,zkw经过一些数学变化,就可以区间修改&区间查询,而且常数极小,比普通线段树小得多。
利用差分,我们可以将区间修改变为O(1)的时间。
首先,我们称原数组为A,得到原数组的差分数组后称之为T,然后将差分数组做前缀和得到数组S,就可以得到原数组的值。

Si=T1+T2+...+Ti=(A10)+(A2A1)+...+(AiAi1)=Ai

所以,从1到k的原数值和就可以这样得出:
i=1kAi=i=1kSi=i=1k(ki+1)Ti=(k+1)Ski=1kiTi

这样我们只需要维护 Ti的前缀和,以及 iTi的前缀和就可以了。
我们记 iTi的前缀和为 Fi,那么最后的区间和公式就是这样的:
i=xyAi=((y+1)SyFy)(xSx1Fx1)

这样就是 O(logn)区间查询,还有,因为修改之后还要调整,所以区间修改也变成 O(logn)的时间了。
附上我丑陋的代码:
code:

#include<bits/stdc++.h>
using namespace std;
int n,m,M;
long long T[410000];
long long f[410000];
long long ff[410000];
long long queryf(int s,int t){
    long long ans=0;
    for(s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1){
        if(~s&1)ans+=f[s^1];
        if(t&1)ans+=f[t^1];
    }
    return ans;
}
long long queryff(int s,int t){
    long long ans=0;
    for(s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1){
        if(~s&1)ans+=ff[s^1];
        if(t&1)ans+=ff[t^1];
    }
    return ans;
}
void add(int s,long long v){
    f[s+M]+=v;
    ff[s+M]=s*(f[s+M]);
    s+=M;
    for(s>>=1;s;s>>=1){
        f[s]=f[s<<1]+f[s<<1|1];
        ff[s]=ff[s<<1]+ff[s<<1|1];
    }
}
int main(){
    scanf("%d %d",&n,&m);
    for(M=1;M<=n+1;M<<=1);
    for(int i=1;i<=n;i++){
        scanf("%lld",&T[i+M]);
    }
    for(int i=M+1;i<=M+n;i++){
        f[i]=T[i]-T[i-1];
        ff[i]=(i-M)*f[i];
    }
    for(int i=M-1;i>=1;i--){
        f[i]=f[i<<1]+f[i<<1|1];
        ff[i]=ff[i<<1]+ff[i<<1|1];
    }
    for(int i=1;i<=m;i++){
        int tmp;
        scanf("%d",&tmp);
        if(tmp&1){
            int x,y;
            long long k;
            scanf("%d %d %lld",&x,&y,&k);
            add(x,k);
            add(y+1,-k);
        }
        else{
            int x,y;
            scanf("%d %d",&x,&y);
            printf("%lld\n",(y+1)*queryf(1,y)-queryff(1,y)-(x)*queryf(1,x-1)+queryff(1,x-1));
        }
    }
    return 0;
}

贴一下时间效率区别:
这是普通线段树:
这里写图片描述
这是zkw线段树:
这里写图片描述
差距竟然如此之大,常数小就是不一样啊。。


之后就是废话了,这个zkw还是非常不实用的,我不建议大家用,最好是用zkw的思想去写一棵真正的线段树,效率较高,实用;虽然我还没写(手动滑稽)

转载于:https://www.cnblogs.com/stone41123/p/7581283.html

相关文章:

  • GraphicsStatsService之1-dump数据的实现
  • Nginx(转)
  • react-create-app
  • 好用的Vue状态管理模式:浅谈Vuet在实际应用中解决的问题
  • Android 解决 View 的滑动冲突
  • RabbitMQ-Java版本生产与消费
  • Ajax学习(一)
  • window对象
  • saltstack常用远程命令
  • vuex,vue问题汇集(一)
  • ERROR   OGG-01161 Bad column index (15) specified for table
  • HNUSTOJ-1520 压缩编码
  • java json与map互相转换(一)
  • 『TensotFlow』RNN中文文本_上
  • 高并发网络编程之epoll详解(转载)
  • JavaScript 如何正确处理 Unicode 编码问题!
  • 【402天】跃迁之路——程序员高效学习方法论探索系列(实验阶段159-2018.03.14)...
  • 【MySQL经典案例分析】 Waiting for table metadata lock
  • 【node学习】协程
  • es6要点
  • linux安装openssl、swoole等扩展的具体步骤
  • Linux编程学习笔记 | Linux IO学习[1] - 文件IO
  • Linux链接文件
  • passportjs 源码分析
  • Perseus-BERT——业内性能极致优化的BERT训练方案
  • Python实现BT种子转化为磁力链接【实战】
  • React 快速上手 - 07 前端路由 react-router
  • REST架构的思考
  • SQLServer之创建显式事务
  • underscore源码剖析之整体架构
  • 阿里云前端周刊 - 第 26 期
  • 理解 C# 泛型接口中的协变与逆变(抗变)
  • 聊聊sentinel的DegradeSlot
  • 七牛云假注销小指南
  • 如何用vue打造一个移动端音乐播放器
  • 实现简单的正则表达式引擎
  • 手写双向链表LinkedList的几个常用功能
  • 吴恩达Deep Learning课程练习题参考答案——R语言版
  • 原生 js 实现移动端 Touch 滑动反弹
  • # Panda3d 碰撞检测系统介绍
  • #gStore-weekly | gStore最新版本1.0之三角形计数函数的使用
  • #Linux(帮助手册)
  • $$$$GB2312-80区位编码表$$$$
  • (四)Tiki-taka算法(TTA)求解无人机三维路径规划研究(MATLAB)
  • (原創) 是否该学PetShop将Model和BLL分开? (.NET) (N-Tier) (PetShop) (OO)
  • (转)Linq学习笔记
  • (转载)OpenStack Hacker养成指南
  • .net core 3.0 linux,.NET Core 3.0 的新增功能
  • .NET Core实战项目之CMS 第十二章 开发篇-Dapper封装CURD及仓储代码生成器实现
  • .net 流——流的类型体系简单介绍
  • .NET 设计一套高性能的弱事件机制
  • .NET 同步与异步 之 原子操作和自旋锁(Interlocked、SpinLock)(九)
  • .net打印*三角形
  • .NET基础篇——反射的奥妙
  • /proc/stat文件详解(翻译)