首页 > 其他 > 详细

提高篇6--字符串专题

时间:2020-09-21 23:44:23      阅读:58      评论:0      收藏:0      [点我收藏+]

字符串hash进阶

  字符串hash是指将一个字符串S映射为一个整数
  使该整数可尽可能唯一代表字符串S

KMP算法

专题扩展

树状数组

  lowbit(x)=x&(-x)可理解 为能整除x的数&同时为2的幂的数构成一个集合,取其中最大的数,即为结果
  
  给出一个整数序列A
  元素个数为N[N<=10^5]
  接下来查询K次[K<=10^5]
  每次查询将给出一个正整数x[x<=N]
  求前x个整数之和


  升级
  假设查询过程中可能随时给第x个整数加上一个整数v
  要求在查询中能实时输出前x个整数之和[更新操作和查询操作的次数总和为K次]
  树状数组仍然是一个数组
  是一个用来记录和的数组
  它存放的是在i号位之前[含i号位]lowbit(i)个整数之和


  树状数组定义:
  对于数组A[1~N][注意索引从1开始]
  数组A的树状数组为C[1~N]
  C[i]的求解,首先通过lowbit(i)得到一个数k,则从A[i]往前的k个数之和即为C[i]

  - 设计函数getSum(x),返回前x个数之和
  - 设计函数update(x, v),实现将第x个数加上一个数v的功能,即为A[x]+=v
  记
  SUM(1,x)=A[1]+...+A[x]
  =SUN(1,x-lowbit(x))+C[x]
  如此可将求和的时间复杂度由O(N)变为O(lg(N))


  如何设计update(x,v),给第x个数加上一个v
  可对应让C[i]中用到第x个数的C[i]均加上一个v
  总是寻找离当前C[x]最近的能覆盖C[x]的C[y]
  
  让x不断加上lowbit(x),确定每个更新的C[i]位置
  时间复杂度为O(lg(N))


  给定一个有N个正整数的序列A[N<=10^5,A[i]<=10^5]
  对序列中的每个数,
  求出序列中它左边比它小的数的个数

提高篇6--字符串专题

原文:https://www.cnblogs.com/raindayinrain/p/13709178.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!