树状数组及例题（含题解）（持续更新）

本是古典何须时尚 2024-04-17 05:55 46阅读 0赞

# 树状数组及例题（含题解）（持续更新） #

和线段树不同的是，树状数组的代码量相对而言较少，而且感觉比线段树容易理解，但是也就是板子题简单

稍微变形，恐怕就有点难了

但是有个板子题，树状数组和线段树都可以解决的就是求区间和，（当然如果单纯的求区间和的话，前缀和是个不错的选择），但是如果需要修改元素的话，前缀和的时间复杂度可就远比树状数组和线段树要大了

个人觉得如果就这个问题而言的话，还是树状数组要好点，毕竟代码短，而且容易理解，操作更方便

树状数组的核心感觉就是那个**lowbit**

至于具体原理什么的，这篇博客是个很不错的选择：

[https://blog.csdn.net/WhereIsHeroFrom/article/details/78922383][https_blog.csdn.net_WhereIsHeroFrom_article_details_78922383]

**例题汇总：**

<table> 
 <thead> 
  <tr> 
   <th>题目链接</th> 
   <th>考察点</th> 
   <th>题解代码</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><font><a href="http://acm.hdu.edu.cn/showproblem.php?pid=1166" rel="nofollow">hdu 1166：敌兵布阵</a></font></td> 
   <td><font>点更新，区间查询（求和）</font></td> 
   <td><font><a href="https://blog.csdn.net/boliu147258/article/details/100057836" rel="nofollow">题解</a></font></td> 
  </tr> 
  <tr> 
   <td><font> <a href="http://acm.hdu.edu.cn/showproblem.php?pid=1754" rel="nofollow">hdu 1754：I Hate It</a></font></td> 
   <td><font>点更新、区间查询（最值）</font></td> 
   <td><font><a href="https://blog.csdn.net/boliu147258/article/details/98352297" rel="nofollow">题解</a></font></td> 
  </tr> 
  <tr> 
   <td><font><a href="http://poj.org/problem?id=2299" rel="nofollow">poj 2299：Ultra-QuickSort</a></font></td> 
   <td><font>树状数组求逆序对、离散化</font></td> 
   <td><font><a href="https://blog.csdn.net/boliu147258/article/details/100057989" rel="nofollow">题解</a></font></td> 
  </tr> 
 </tbody> 
</table>

[https_blog.csdn.net_WhereIsHeroFrom_article_details_78922383]: https://blog.csdn.net/WhereIsHeroFrom/article/details/78922383