CF437BTheChildandSet题解这题目就一个问题。啥是\(\operatorname{lowbit}\)？\(\operatorname{lowbit}(x)\)是指\(x\)的二进制表示中最低位的\(1\)所表示的值。例如\((14)_{10}=(1110)_2\)，其中最低位的\(1\)在第二位，表示\((2)_{10}\)，即\(\operatorname{lo

树状数组（BinaryIndexedTree,BIT）树状数组（BinaryIndexedTree,BIT），也称为FenwickTree，是一种用于高效处理数组前缀和查询和单点更新的数据结构。它能够在(O(\logn))时间内完成单点更新和前缀和查询操作。基本概念前缀和：给定一个数组a，前缀和prefix_sum[i]表示a[0]+

单点增加，范围查询inttree[MAXN][MAXM];intnums[MAXN][MAXM];intn,m;intlowbit(inti){returni&-i;}voidadd(intx,inty,intv){for(inti=x;i<=n;i+=lowbit(i)){for(intj=y;j<=m;j+=lowbit(j)){

什么是树状数组树状数组是一种码量小，常数小，支持单点修改和区间查询的数据结构。树状数组维护的信息和运算需要满足结合律并且可差分注意gcd和max操作虽然满足结合律，但不可差分，因此不能使用树状数组维护其实，树状数组能做的，线段树都能做，线段树能做的，树状数组不一定能做，但线段树

中学的时候年轻气盛，应该拿主席树把这道题艹过去了。正好复习离线二维数点，再做了一遍。我们把询问差分安排到x轴上，然后y轴用树状数组统计即可。注意到此题要离散化，但是询问中的x可能不在原序列中。不过这不要紧，记得二分完减一就好。constintN=5e5+5,S=1e7+5;intn,m

数据结构栈栈，一种基本的先进后出的线性数据结构，手写栈一般有一个指针指向栈顶元素。STL中有个容器叫stack,支持一些功能push,将元素放置在栈顶；top(),输出栈顶元素pop()，弹出栈顶元素size(),访问栈中元素clear，清空详细操作可以见栈手写栈可以用数组模拟栈，代码如下。

constintN=5e5+5;constintINF=0x3f3f3f3f;intn,q;inta[N],trmx[N],trmn[N];//将原来的累加改为求最值voidadd(intx,intk){while(x<=n){trmx[x]=max(trmx[x],k);trmn[x]=min(trmn[x],k);x+=lowbit(x);}}//区间查询最大/小值

网络赛复现地址：https://codeforces.com/gym/105336 L网络预选赛：做法：直接枚举两行两列即可代码：#include<bits/stdc++.h>usingnamespacestd;constintN=510;chara[N][N];intmain(){intn,m;cin>>n>>m;for(inti=0;i<n;i++)for

前言树状数组，即树形存储的数组，又称BinaryIndexedTree或FenwickTree。抛开它树形的存储结构，这种神奇的数据结构的应用看起来与「树」没什么关系：有一个序列\(A=(A_1,A_2,\dots,A_N)\)，在不超过\(\mathcalO(\logN)\)的时间复杂度内完成下列操作：\(\to~\)求\([L,R]\)区间内所

0.前言突然想到位运算是个好东西，就来水一波文章了……注意：我把能想到的有关位运算的所有内容都放进来了，所以篇幅较长，请谅解！若有写的不清楚或者不够详细的地方欢迎在评论区补充，谢谢支持！本文中参考代码均使用C++编写。废话不多说，下面步入正题。1.基本运算有一定基础的可以

树状数组用于变化区间的动态维护进行\(O(logn)\)的插入和删除。\(lowbit(x)\)表示二进制表示中最低位的1代表的值称为最小位值，实际上就是二进制表示中最低位的1代表的值称为最小位值二进制表示中最低位的1加上后面的0的值。设树状数组\(c\)，\(c_i\)表示${\textstyle\sum

功能1：判断一个数字\(x\)二进制下第\(i\)位是不是等于\(1\)if((1<<(i-1))&x)将1左移i-1位,相当于制造了一个只有第i位上是1,其他位上都是0的二进制数。然后与x做与运算如果结果\(>0\)说明x第i位上是1，反之是0功能2：将一个数字x二进制下第i位更改成1x=x|(1<<(i-1))

https://www.luogu.com.cn/problem/P1972莫队算法被卡，只能得60points正解有点像基于贪心的fenwicktree策略fenwick的每个位置表示当前位置上是否是某个数的最后一次出现位置，值为0或者1右指针升序排序，然后右指针移动过程中更新每个数最后一次出现的位置而不管左指针如何变，只

1cfdiv951位运算（异或）https://www.luogu.com.cn/problem/CF1979B思路[l,r]=[l1,r1]^(x^y)也就是是找x^y异或一个区间后仍然能够连续，对于x^y可以写成xxxx1000，xxxx设为A，为一段01序列，那么就是区间[0,x^y-A-1]能够保证连续。因为第一个1右侧都是0，都不进位，1000+0000，100

思路不难想，细节比较多。思路观察到\(n\le19\)，首先想到状压dp。于是自然地定义\(dp[j][i]\)为：抵达点的状态为\(i\)，且此时在点\(j\)时，简单路径的条数。注意这里是简单路径的条数，而不是环的个数，因为环的个数要在dp过程中统计。这里的dp作用就在于求简单路径条数。

树状数组一、单点修改和区间查询lowbit函数\[lowbit(x)=x\&(-x)\]作用：得到\(x\)二进制最右侧的1。如，\(x=(0010010011000)_2\)，则\(-x=x取反+1=(1101101101000)_2\)，\(x\&(-x)=(0000000001000)_2\)。原理用\(c[i]\)表示树状数组，\(a[i]\)表示原数组。将\(c[i]\)

hanghangakioi考试的时候在乱猜结论，交了几遍就过了，证明当然是赛后才想的（）文中加粗部分是需要读者稍微思考一下原因的地方（不是重点）。先考虑一下样例二，将\(10^{18}\)化成二进制：\(1101...001000000000000000000\)。其实只需要知道末尾有\(18\)个\(0\)就行了，因为在\(x\)

发明这个的人真的变态啊！！！！！！！！！！一，概念树状数组是一种基于二进制思想的数据结构，基本用途是维护序列的前缀和。对于给定的序列a,设树状数组为c，则c[x]保存序列a的区间[x-lowbit(x)+1,x]中所有数的和二，lowbit()操作 作用：求一个数字二进制的第一个为1的位置和后面的0构成的数值 操

什么是树状数组顾名思义就是一个结构为树形结构的数组，于二叉树的结构类似但又不同，它是在二叉树的结构上删除了一些中间节点，来看两幅图就明白了.1.这是二叉树的结构 2.这是树状数组的结构 不难发现，树状数组相比于二叉树删除了一些节点，但是为什么要删除呢？这就和树状数组的

笔记完整版链接参照oi.wiki整理了基础dp的一些笔记：学习笔记+模板（Adorable_hly）（自己结合网络和做题经验总结的，dalao勿喷）第一大板块：DP动态规划适用场景：1.最优化原理：若该问题所包含的子问题解是最优的，就称该问题具有最优子结构，满足最优化原理。2.无后效性：指某一阶段的状

lowbit的定义首先了解lowbit的定义\(lowbit(n)\)，为\(n\)的二进制原码中最低的一位\(1\)以及其后面的\(0\)所表示的数举个简单的例子：将\(10\)使用二进制表示为\(1010\)其中最低位的\(1\)为第2位（\(_{10}1_0\)，从右往左数）此时\(lowbit(10)\)使用二进制表示为

高效维护区间之和/区间最值的数据结构(一)——树状数组树状数组的核心思想：分治。将数组以二叉树的形式进行维护区间之和。设aaa为原数组，

知识点1：lowbit(x)        简介：众所周知，lowbit()操作是算法竞赛中的高级技巧，特别是高级数据结构，线段树的核心，还有什么二进制与位运算题目，而本文就用最通俗易懂的话，来教会大家lowbit的含义。        含义：lowbit(x)是x的二进制表达式中最低位的1所对应的值。

原题链接：https://www.luogu.com.cn/problem/P1036题意解读：题目即要在n个数中，枚举出所有的子集，当子集中数字个数刚好为k时，求和，判断是否是素数。解题思路：方法一：二进制法通过二进制法，可以枚举一个集合中所有元素“选”或者“不选”的情况，用二进制1表示选该元素，二进制0表示不选。

link：https://codeforces.com/problemset/problem/1967/C题意：定义\(f(a)=s\)中的\(f\)表示把序列\(a\)映射为其树状数组的操作（\(s\)就是对应的树状数组），并且操作是在取模下作的，已知\(f^k(a)=b\)，已知序列\(b\)和自然数\(k\)，求\(a\).\(1\leqn\leq2\times10^5,1\leq