题意：
定义B ( x )表示x的二进制形式中1的个数，F ( x ) = m i n ( y ∣ y > x & B ( y ) < = B ( x ) )
给出n，对于x < = n，如果F ( x ) < = n，那么x的父节点是F ( x )；否则，则x为根。
两种操作，每次给出o p , u , v
如果o p = = 1的话，让u以及所有祖先节点的权值都+ v
如果o p = = 2的话，询问[ u , v ]的权值的和
思路：
F(x)=x+lowbit(x)
这样每次最多修改l o g n个节点，相当于单点修改区间查询，用树状数组维护一下。时间复杂度是m l o g 2 n修改的函数就会这样写：
for(ll i=u;i<=n;i+=lowbit(i)) update(i,v);//树状数组的单点修改函数
根据树状数组的性质，可以简化为下面这样：
ll num=1; while(pos<=n){ tr[pos]+=val*num; num++,pos+=lowbit(pos); }
这样就会将修改的复杂度降到l o g n
常理说用u n o r d e r e d _ m a p就可以卡过去了，但是一直在t，只能换了手写的哈希表
存哈希表板子
const int H=8300597; struct hash_map { int la[H],top; struct E { LL key,da; int ne; } e[int(3e6+5)]; void clear(){ memset(la,0,sizeof(la)); top=0; } bool count(LL k){ static int i; i=la[k%H]; while (i&&e[i].key!=k) i=e[i].ne; return i; } LL& operator[] (LL k){ static int h,i; i=la[h=k%H]; while (i&&e[i].key!=k) i=e[i].ne; if (!i) { e[i=++top]=(E){k,0,la[h]}; la[h]=top; } return e[i].da; } } a;
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll #define tpyeinput long long inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;} inline void read(tpyeinput &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();} #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} //const int maxn = 1e5 + 10; const int maxn=2e6+10,mod=8300597; struct Hash { ll e,next; ll w; }edge[maxn]; ll head[mod],cnt=0; void Init() { memset(head,-1,sizeof(head)); cnt=0; } void Insert(ll x,ll val) { ll temp=x%mod; for(ll i=head[temp];~i;i=edge[i].next) { if(edge[i].e==x) { edge[i].w+=val; return ; } } edge[cnt]=Hash{x,head[temp],val}; head[temp]=cnt++; } ll Find(ll x) { ll temp=x%mod; for(int i=head[temp];~i;i=edge[i].next) { if(edge[i].e==x) return edge[i].w; } return 0ll; } ll n,m; ll lowbit(ll x){return x&-x;} ll qask(ll pos){ ll ans=0; while(pos){ ans=ans+Find(pos); pos-=lowbit(pos); } return ans; } int main() { Init(); read(n);read(m); while(m--){ ll op,u,v; read(op);read(u);read(v); if(op==1){ ll pos=u,val=v; ll num=1; while(pos<=n){ Insert(pos,val*num); //table.adde(pos,val*num); num++,pos+=lowbit(pos); } } else{ ll ans=qask(v)-qask(u-1); printf("%lld\n",ans); } } return 0; } /* */
![[蓝桥杯][历届试题]九宫重排（BFS+哈希）](https://ucc.alicdn.com/pic/developer-ecology/83478858217d49f4b0fcab5361118392.png?x-oss-process=image/resize,h_160,m_lfit)
