目录前言树状数组  lowbit函数  直观表述    代码   运行结果树状数组构建代码树状数组的应用  单点修改和（单点）区间查询  结合差分数组区间修改,单点查询        差分数组Colortheballhdu1556  问题描述  问题分析

发现大多数的题解都是不同于官方题解的做法，这里我将介绍官方题解做法。Solution证明先手是否可以必胜的方法相差无几，为了方便后边行文，这里介绍我的思路：考虑各堆石子和为奇数的情况（以下简称为“奇状态”，另一种称为“偶状态”）一定先手必胜：两人一次取一个即可。考虑偶状态。可以发

原题链接：https://www.luogu.com.cn/problem/P3374题意解读：树状数组模版：单点修改，区间求值。解题思路：树状数组-BinaryIndexTree可以动态维护一组数，可以O(logn)的修改一个数，也可以O(logn)的计算一段区间的和。思考一下朴素做法：如何修改一个数，计算区间和？如果是常规数组，修改操作

 loj传送门https://loj.ac/p/2211洛谷题目传送门https://www.luogu.com.cn/problem/P3287解题思路首先，我们可以贪心地思考一下：对于每一次区间的加一操作，右端点是在末尾会比右端点在中间的情况更好。因为，当你的右端点在序列中间的时候，相对之下，后面的数就更小了一些，这样是

CodeforcesGlobalRound27总结A将红色的位置\((r,c)\)移走，分为三块来考虑，蓝色的块移动\(m-c\)，黄色的块移动\(m*(n-r)\)，绿色的块移动\((m-1)*(n-r)\)。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#in

lowbitlowbit在竞赛中还是很常见的，比如树状数组就必须要用lowbit。lowbit的原理是利用原码,反码,补码的性质来获得数字在二进制下最低位的\(1\)。理解了原码，反码，补码，就不难理解lowbit了。lowbit代码如下：inline int lowbit(int x) {    return x & -x;

位运算笔记对二进制数进行直接操作：基础操作：例：a=00001101;b=00110101;与：a&b==00000101;//当两个数的第i位都为1时，a&b的第i位才为1或：a|b==00111101;/*当两个数的第i位都为0时，a|b的第i位才为0或者说两个数的第i位其中至少有一个为1，对应的a|b的第i位就为1*/

P9890[ICPC2018QingdaoR]Tournament题目传送门更好的阅读体验一道找规律的思维题。前置知识\(lowbit\)\(lowbit\)是指获取一个二进制数中最右边的\(1\)所对应的数值。具体地，\(lowbit\)可以通过对一个数取反然后加\(1\)，再与原数进行按位与的方式来实现。intlow

前言这两天在网上学树状数组，但是发现网上关于树状数组的解释大都对初学者不太友善，原理讲解部分并不是很容易理解，所以写了一篇树状数组，顺便帮自己巩固一下。一、什么是树状数组1.概念：简单来说，这是一种数据结构。顾名思义，它通过树的结构来对数组进行高效操作，一般用于求数组前缀

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作用就在于求简单路径条数。