首页 > 代码库 > 有关数据结构的知识17.5.1清北

有关数据结构的知识17.5.1清北

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<queue>
  5 #include<stack>
  6 #include<map>
  7 //#include<unordered_map>
  8 
  9 using namespace std;
 10 
 11 **********重载运算符************* 
 12 struct rec
 13 {
 14     int a,b;
 15     bool operator<(const rec &c)const
 16     {
 17         if (a==c.a) return b>c.b;
 18         else return a>c.a;
 19     }
 20 }g,gg;
 21 ****************链表************ 
 22 int v[maxn],next[maxn],cnt;
 23 
 24 void zou()链表移动 
 25 {
 26     int p=1;
 27     int sum=0;
 28     while (p!=0)
 29     {
 30         sum+=v[p];
 31         p=next[p];
 32     }
 33 }
 34 
 35 void charu(int p,int w)链表插入 
 36 {
 37     cnt++;
 38     v[cnt]=w;
 39     next[cnt]=next[p];
 40     next[p]=cnt;
 41 }
 42 ************栈***队列***堆***********8 
 43 int main()
 44 {
 45     g<gg;
 46     int x;
 47     queue<int> que;
 48     que.push(x);
 49     int y=que.front();
 50     que.pop();
 51     que.size();
 52 
 53     stack<int> sta;
 54     sta.push(x);
 55     int z=sta.top();
 56     sta.pop();
 57     sta.size();
 58 
 59     priority_queue<rec> heap;
 60     heap.push(x);
 61     int r=heap.top();
 62     heap.pop();
 63     heap.size();
 64 }
 65 *************并查集 ****************
 66 int f[maxn];
 67 
 68 for (int a=1;a<=n;a++)
 69     f[a]=a;
 70 
 71 int getf(int now)
 72 {
 73     if (f[now]==now) return now;
 74     else return f[now]=getf(f[now]);
 75 }
 76 
 77 int merge(int p1,int p2)
 78 {
 79     f[getf(p1)]=getf(p2);
 80 }
 81 
 82 bool same(int p1,int p2)
 83 {
 84     return getf(p1)==getf(p2);
 85 }
 86 ****************hash****************
 87 map<long long,int> ma;
 88 map<string,int>;
 89 map<rec,int>;
 90 
 91 ma[num]=ma[num]+1;
 92 ma[num];
 93 ***************线段树************ 
 94 ***************递归************** 
 95 int a[maxn];
 96 
 97 int sum[maxn*4];
 98 
 99 void update(int rt)
100 {
101     sum[rt]=sum[rt*2]+sum[rt*2+1];
102 }
103 
104 void build(int l,int r,int rt)建立从l到r标号st 
105 {
106     if (l==r)到最后节点 
107     {
108         sum[rt]=a[l];
109         return;
110     }
111     int m=(l+r)/2;
112     //int m=(l+r)>>1;
113     build(l,m,rt*2);建立左边 
114     //build(l,m,rt<<1);
115     build(m+1,r,rt*2+1);建立右边 
116     //build(m+1,r,rt<<1|1);
117     ***********全部分离********** 
118     update(rt);填入数 
119 }
120 ***********修改 
121 void modify(int l,int r,int rt,int p,int v)
122 {
123     if (l==r)进行到最后 
124     {
125         sum[rt]=v;进行修改 
126         return;
127     }
128     int m=(l+r)/2;
129     if (p<=m) modify(l,m,rt*2,p,v);
130     else modify(m+1,r,rt*2+1,p,v);全部分离 
131     update(rt);将修改后的状态全部改变 
132 }
133 ***********求从nowl到nowr的值 
134 int query(int l,int r,int rt,int nowl,int nowr)
135 {
136     if (nowl<=l && r<=nowr) return sum[rt];此区间l到r被nowl和nowr完全包含住就返回此线段的值 
137     int m=(l+r)/2;继续分离 
138     int ans=0;
139     if (nowl<=m) ans+=query(l,m,rt*2,nowl,nowr);和左边有交集  询问左边 
140     if (m<nowr) ans+=query(m+1,r,rt*2+1,nowl,nowr);和右边有交集  询问右边 
141     return ans;
142 }
143 
144 scanf("%d",&n);
145 for (int b=1;b<=n;b++)
146     scanf("%d",&a[b]);
147 build(1,n,1);
148 modify(1,n,1,p,v);
149 query(1,n,1,nowl,nowr);
150 ***************** 
151 notonlysuccess
152 
153 *******************树状数组********* 
154 简介:
155     对于一个数组求其l到r的值的和,即从l--r;利用分治(类似规定)算(2^lowbit(x)--r)+(l--r);再将2^lowbit(x)递归进行分解;
156     lowbit(x)是指将x转化为2进制后,从低位到高位第1个"1"的位置即第几位(从0开始数)例如;lowbit(6)=1;6的2进制为110,即2;
157     求[1,7]等价于     [7,7]        +           [1,6]
158              对应2^lowbit(7)--7          1--2^lowbit(7)
159     而[1,6]等价于     [4,5]        +          [1,4]    
160               对应 2^lowbit(4)--4         1-- 2^lowbit(4);
161               
162 **************树状数组********* 
163 lb(x) = 2^lowbit(x)
164 
165 int lb(int x)
166 {
167     return x&(-x);取出将x转换为3进制后最后一个1;例x  0001000,则-x 1111000即从最后一个1开始往前取反;然后进行与运算相同为1,不同为0 
168 }
169 
170 z : 树状数组 
171 y : 数组 
172 
173 void modify(int p,int v)修改 将p位置的数改为v 
174 {
175     int delta=v-y[p];将p后面的数都加上(更改的数-原来的数)
176     y[p]=v;更改 
177     for (;p<=n;p+=lb(p))+= 2^lowbit(x)
178         z[p]+=delta;树状数组进行更改 
179 }
180 
181 int query(int p)询问 
182 {
183     int ans=0;
184     for (;p;p-=lb(p))按照lb(p)的顺序进行 
185         ans+=z[p];
186     return ans;
187 }
188 *****************树状数组伪***************
189 #include<iostream>
190 using namespace std;
191 int n,m,i,num[100001],t[200001],l,r;//num:原数组;t:树状数组 
192 int lowbit(int x)
193 {
194     return x&(-x);
195 }
196 void change(int x,int p)//将第x个数加p 
197 {
198     while(x<=n)
199     {
200         t[x]+=p;将树状数组中第x 
201         x+=lowbit(x);
202     }
203     return;
204 }
205 int sum(int k)//前k个数的和 
206 {
207     int ans=0;
208     while(k>0)
209     {
210         ans+=t[k];
211         k-=lowbit(k);
212     }
213     return ans;
214 }
215 int ask(int l,int r)//求l-r区间和 
216 {
217     return sum(r)-sum(l-1); 
218 }
219 int main()
220 {
221     cin>>n>>m;
222     for(i=1;i<=n;i++)
223     {
224         cin>>num[i];
225         change(i,num[i]);
226     }
227     for(i=1;i<=m;i++)
228     {
229         cin>>l>>r;
230         cout<<ask(l,r)<<endl;
231     }
232     return 0;
233 } 
234 *************涂色************ 
235 for (int a=m;a>=1;a--)
236 {
237     for (int b=getf(l[a]);b<=r[a];b=getf(b+1))
238     {
239         if (!color[b]) ans[b]=color[b];
240         f[getf(b)]=getf(r[a]);
241     }
242 }
243 *************分块***************** 
244 int s=sqrt(n);分成块的大小为sqrt(n); 
245 for (int i=1;i<=n;i++)
246     belong[i]=(i-1)/s+1;belong[i]数组表示第i个数所在的块 
247 int cnt=belong[n];一共有几块 
248 
249 for (int i=1;i<=cnt;i++)
250 {
251     sum[i]=add[i]=0;sum表示此时第i块的总值为几,add表示第i块添加的数的总和 
252     if (i==cnt)防止最后一块不足s,size表示每一块的长度 
253     {
254         if (n%s==0) size[i]=s;
255         else size[i]=n%s;
256     }
257     else size[i]=s;
258 }
259 for (int i=1;i<=n;i++)
260     sum[belong[i]]+=a[i];i所属的那一块的sum加上ai 
261 
262 int query(int l,int r)访问 
263 {
264     int ans=0;
265     if (belong[l]==belong[r]) ans-=sum[belong[l]];此处为避免l与r属于同一块画图很好理解,此处不再解释 
266     while (belong[l]==belong[l-1])
267     {
268         ans+=a[l]+add[belong[l]];因为l要++,所以l会遍历在从l到r的不整区间中所有的数,so要加a数组 **从左到第一个整区间 
269         l++;
270     }
271     while (belong[r]==belong[r+1])**从最后一个整区间到最后 
272     {
273         ans+=a[r]+add[belong[r]];
274         r--;
275     }
276     for (int i=belong[l];i<=belong[r];i++)加入所有整区间的数 
277         ans+=sum[i];
278     return ans;
279 }
280 
281 void modify(int l,int r,int v)修改 
282 {
283     if (belong[l]==belong[r])属于同一分块 
284     {
285         for (int i=l;i<=r;i++)so easy 
286             a[i]+=v;
287         return;
288     }
289     while (belong[l]==belong[l-1])自此往下同上访问 
290     {
291         a[l]+=v;
292         l++;
293     }
294     while (belong[r]==belong[r+1])
295     {
296         a[r]+=v;
297         r--;
298     }
299     for (int i=belong[l];i<=belong[r];i++)
300     {
301         add[i]+=v;
302         sum[i]+=size[i]*v;
303     }
304 }

相信你会收获很多**********

有关数据结构的知识17.5.1清北