树状数组（区间维护/单点修改）
创始人
2025-06-01 20:45:24
0次

1，定义

数组数组用于维护区间信息，简洁的几行的代码可以单点操作/区间查询，或者区间操作与单点查询。

虽然功能小于线段树，但是在相同功能的实现上，两者复杂度差不多。线段树

2，实现思路

树状数组有两个功能，一个是单点修改，区间（单点）查询。一个是区间修改，但是只能单点查询。两个功能不能同时使用。

我们先介绍第一个功能

先看一下树状数组的图

 我们观察出他的几个性质：

  1. 最外层的t是2的倍数（只有一个1），而且他的t[x]的值是a[1]+...+a[x]
  2. 每个点的父亲都是该点加上自己的最低位1就可得到如0010，最低位是10，0010+10=0100，就是父亲。
  3. 我们求x的1到x的前缀和，假设x=7，那么sum[7]=t[7]+t[6]+t[4],发现每次都是不断减去最低位1，直到最外层，即7-lowbit(7)=6,   6-lowbit(6)=4。

我们如何求最低位1呢？

  1. 我们知道：-x等价于x取反+1,假设x=10110，~x=01001,~x+1=01110。注意到-x与x的最低位1同位，其他高位全部不同，这是偶然吗？
  2. 我们对x取反，那么~x与x所有位不同，但是加上1后，再遇到最低位第一个0前，1全部变成0，不断往前推进（使得本来不同变得相同），当遇到0后，1被0吸收变成1，不再往后了，那么后面的高位仍然保持所有位不同。这样，我们把-x&x得到的就是lowbit，即最低位1

1，单点操作如何如何区间值更新呢

假如我们对x+k，那么他的祖先们都需要，去祖先的更新方法就是+lowbit

void add(int x,int k)
{for (int i=x; i<=n; i+=i&-i)t[i]+=k;
}

2，区间查询思路简单，我们t表示的是子树的值

那么我们从t[x]一直减最低位1，累加到t[0]即可

ll ask(int x)
{ll ans=0;for (int i=x; i; i-=i&-i)ans+=t[i];return ans;
}

模板题：P3374 【模板】树状数组 1

#include 
using namespace std;
#define ll     long long
const int N = 5e5 + 10;
int a[N],t[N];
int n;
void add(int x,int k)
{for (int i=x; i<=n; i+=i&-i)t[i]+=k;
}ll ask(int x)
{ll ans=0;for (int i=x; i; i-=i&-i)ans+=t[i];return ans;
}int main()
{int m,p,x,y;cin>>n>>m;for (int i=1; i<=n; ++i)cin>>a[i],add(i,a[i]);while (m--){cin>>p>>x>>y;if (p==1){add(x,y);}else if (p==2){cout<

实现功能2

  1. 我们这时只维护单点的值，不再是区间值，所以思路是把原来的数组表示为差分数组，那么原来的x的前缀和就成为x的值

代码没什么区别

int b[N];
int n;
void add(int x,int k)
{for (int i=x; i<=n; i+=i&-i)b[i]+=k;
}
ll ask(int x)
{ll ans=0;for (int i=x; i; i-=i&-i)ans+=b[i];return ans;
}

模板题2：P3368 【模板】树状数组 2

#include 
using namespace std;
#define ll long long
const int N = 5e5 + 10;int b[N];
int n;
void add(int x,int k)
{for (int i=x; i<=n; i+=i&-i)b[i]+=k;
}
ll ask(int x)
{ll ans=0;for (int i=x; i; i-=i&-i)ans+=b[i];return ans;
}int main()
{int m,p,x,y,k;cin>>n>>m;for (int i=1; i<=n; ++i)cin>>x,add(i,x),add(i+1,-x);while (m--){cin>>p;if (p==1){cin>>x>>y>>k;add(x,k),add(y+1,-k);}else if (p==2){cin>>x;cout<

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：Junit4 + Mockito进行单元测试实战案例

下一篇：Linux命令_lsof 网络/文件监控

相关内容

热门资讯

银河证券：短期内A股市场或仍维... 银河证券发布A股策略研报称，近期板块轮动速度加快，行情震荡格局尚未改变，市场成交额未出现明显放量，仍...
哪吒汽车，注定掉队 哪吒汽车，... 定焦One（dingjiaoone）原创特约作者 | 胡锟编辑 | 魏佳从登顶新势力销量冠军，到几乎...
牛市早报｜端午假期预计全社会跨... 【市场数据】截至5月30日收盘，上证综指跌0.47%，报3347.49点；科创50指数跌0.94%，...
黄酒真的雄起了？ 黄酒真的雄起... 斑马消费 杨伟2025年A股酒水板块“冰火两重天”，白酒承压，啤酒失速，黄酒却异军突起！Wind 5...
一台不到600元，魅族新机大火... 对于整个手机市场来说，华米OV等国产手机的市场大战已经日渐稳定，各家手机企业都处于平淡化的状态，就在...
港股稳定币概念暴涨！刘煜辉：人... 6月2日，在港股市场上，数字货币概念股集体拉升，连连数字盘中一度上涨80%，移卡一度涨近50%，欧科...
又现百万罚单 消金合作机构管理... 北京商报讯（记者 岳品瑜 董晗萱）消费金融机构的一张新罚单，又指向合作业务管理。6月2日，北京商报记...
国际金价重返高位 炒金是否卷土... 6月2日，国际金价重返3300美元/盎司高位，截至北京商报记者发稿，金价涨幅超过2%，盘中突破336...
股价翻倍基金霸屏 创新药否极泰... 证券时报记者 裴利瑞今年以来，中国创新药行业正经历了一场前所未有的价值重估，而且在近期呈现加速趋势。...
5000亿人民币新型融资政策工... 内容提要：中国计划推出5000亿元新型政策性金融工具，重点投向新基建与消费领域，以对冲出口压力。但企...
美国5月ISM制造业PMI连续... 6月2日周一，ISM公布的数据显示，美国5月ISM制造业活动连续三个月萎缩，在关税上调的背景下，进口...
国内油价或现年内第四涨 加满一... 　　中新经纬6月3日电 (万可义)国内成品油新一轮调价窗口将于6月3日24时开启。综合机构观点，国内...
道指三连阳！美股6月开门红，黄... *三大股指上扬，纳指涨近0.7%；*中长期美债收益率走高，基准10年期美债报4.61%；*受特朗普言...
结构性行情或延续，券商建议6月... 经历5月冲高回落后，A股6月行情即将拉开帷幕。展望后市表现，当前机构多数持相对谨慎态度，认为市场短期...
马斯克卸任DOGE后旗下公司迎... 马斯克重返其商业帝国、远离政治后，其旗下公司迅速开启一系列融资，包括xAI正在启动一项3亿美元的股份...
媒体称美国秘密提案允许低浓缩铀... 媒体报道，美国对伊核谈判政策出现180度转变，美国政府上周六向伊朗提出一份新的核协议提案，其中允许伊...
一笔漂亮的退出：93亿卖始祖鸟... (图片由豆包AI生成） 消费赛道又一明星公司被减持了。5月29日，据彭博社消息，始祖鸟母公司亚玛芬体...
速腾聚创一季度毛利同比增七成 ... 　　速腾聚创第二代灵巧手Papert 2.0。　　5月30日，速腾聚创发布2025年第一季度财报。据...
“消费+科技”双轮驱动，港股市... 港股IPO市场正经历显著回暖，优质资产供给逐步改善，市场流动性增强，吸引了大量资金关注。Wind资讯...
从一面之恩到千亿帝国CEO，安... 近日，吉利汽车管理层大调整引发行业聚焦。在吉利一季度财报发布的当天，吉利控股集团宣布重大人事调整：极...