schtonn
/
public


			
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237
							<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  

  <title>线段树 | Schtonn&#39;s Blog</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="前置知识
 数组，结构体，二叉树
 引入
 有时候我们会遇到一些大规模的区间查找和区间修改问题，比如让你维护一个 \(10^5\) 长度的数列，要求操作有区间求和、区间加（区间每个数加上一个值），让你在一秒内完成 \(10^5\) 次操作。 暴力是肯定不行的，数据范围太大，会超时。 所以我们就有一种专门解决大范围区间修改查询的数据结构：线段树。">
<meta property="og:type" content="article">
<meta property="og:title" content="线段树">
<meta property="og:url" content="http://yoursite.com/2020/03/02/segment-tree/index.html">
<meta property="og:site_name" content="Schtonn&#39;s Blog">
<meta property="og:description" content="前置知识
 数组，结构体，二叉树
 引入
 有时候我们会遇到一些大规模的区间查找和区间修改问题，比如让你维护一个 \(10^5\) 长度的数列，要求操作有区间求和、区间加（区间每个数加上一个值），让你在一秒内完成 \(10^5\) 次操作。 暴力是肯定不行的，数据范围太大，会超时。 所以我们就有一种专门解决大范围区间修改查询的数据结构：线段树。">
<meta property="og:locale" content="en_US">
<meta property="article:published_time" content="2020-03-02T03:37:36.000Z">
<meta property="article:modified_time" content="2020-03-03T12:40:21.347Z">
<meta property="article:author" content="Schtonn">
<meta property="article:tag" content="graph">
<meta name="twitter:card" content="summary">
  
    <link rel="alternate" href="/atom.xml" title="Schtonn&#39;s Blog" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  
<link rel="stylesheet" href="/css/style.css">

<meta name="generator" content="Hexo 4.2.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">Schtonn&#39;s Blog</a>
      </h1>
      
        <h2 id="subtitle-wrap">
          <a href="/" id="subtitle">Schtonn&#39;s blog</a>
        </h2>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/">Home</a>
        
          <a class="main-nav-link" href="/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="Search"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://yoursite.com"></form>
      </div>
    </div>
  </div>
</header>
      <div class="outer">
        <section id="main"><article id="post-segment-tree" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2020/03/02/segment-tree/" class="article-date">
  <time datetime="2020-03-02T03:37:36.000Z" itemprop="datePublished">2020-Mar-02</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      线段树
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h3 id="前置知识">前置知识</h3>
<p>数组，结构体，二叉树</p>
<h3 id="引入">引入</h3>
<p>有时候我们会遇到一些大规模的区间查找和区间修改问题，比如让你维护一个 <span class="math inline">\(10^5\)</span> 长度的数列，要求操作有区间求和、区间加（区间每个数加上一个值），让你在一秒内完成 <span class="math inline">\(10^5\)</span> 次操作。 暴力是肯定不行的，数据范围太大，会超时。 所以我们就有一种专门解决大范围区间修改查询的数据结构：线段树。</p>
<a id="more"></a>
<h3 id="线段树">线段树</h3>
<p>线段树本质上是把整个数列拆分了，用一个一个区间来表示。 比如有 <span class="math inline">\(n\)</span>个节点 根节点代表整个数列的区间<span class="math inline">\([1,n]\)</span>， 根节点的两个子节点代表根区间二分成两部分，也就是 <span class="math inline">\([1,\operatorname{mid}]\)</span> 和 <span class="math inline">\([\operatorname{mid},n]\)</span>。 而子节点也是一棵线段树。 一直往下眼神，叶子结点就代表着单一位置<span class="math inline">\([a,a]\)</span></p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2020/03/02/segment-tree/" data-id="ck7cjuv730004pc13034b6qa3" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/graph/" rel="tag">graph</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
  
    <a href="/2020/03/02/ferbonacci/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Older</strong>
      <div class="article-nav-title">斐波那契数列-O(1)</div>
    </a>
  
</nav>

  
</article>

</section>
        
          <aside id="sidebar">
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tags</h3>
    <div class="widget">
      <ul class="tag-list" itemprop="keywords"><li class="tag-list-item"><a class="tag-list-link" href="/tags/graph/" rel="tag">graph</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/math/" rel="tag">math</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/other/" rel="tag">other</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/struct/" rel="tag">struct</a></li></ul>
    </div>
  </div>


  <div class="widget-wrap">
    <h3 class="widget-title">Tag Cloud</h3>
    <div class="widget tagcloud">
      <a href="/tags/graph/" style="font-size: 20px;">graph</a> <a href="/tags/math/" style="font-size: 10px;">math</a> <a href="/tags/other/" style="font-size: 15px;">other</a> <a href="/tags/struct/" style="font-size: 10px;">struct</a>
    </div>
  </div>

  
  <div class="widget-wrap">
    <h3 class="widget-title">Archives</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/03/">March 2020</a></li></ul>
    </div>
  </div>


  <div class="widget-wrap">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/2020/03/02/segment-tree/">线段树</a>
          </li>
        
          <li>
            <a href="/2020/03/02/ferbonacci/">斐波那契数列-O(1)</a>
          </li>
        
          <li>
            <a href="/2020/03/02/dinic/">网络最大流-Dinic</a>
          </li>
        
          <li>
            <a href="/2020/03/01/min-span-tree/">最小生成树</a>
          </li>
        
          <li>
            <a href="/2020/03/01/union-find/">并查集</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2020 Schtonn<br>
      Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>
    </div>
    <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    

<script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>


<link rel="stylesheet" href="/fancybox/jquery.fancybox.css">

  
<script src="/fancybox/jquery.fancybox.pack.js"></script>


<script src="/js/script.js"></script>


  </div>
</body>
</html>