搜索结果
查询Tags标签： 树状，共有 66条记录-
AcCoders 7961 Problem D：【省选基础数据结构 树状数组】树状数组 题解
树状数组板子，单点修改，区间查询，注意处理读入字符的问题。 //7961 Problem D：【省选基础数据结构 树状数组】树状数组 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=100005; ll c[MAXN],a[MAXN],n; #define lowbit(x)…
2022/9/10 23:23:31 人评论 次浏览 -
算法提高课 第四章 数据结构之树状数组
一、介绍 功能快速求前缀和 O(logn) 修改某一个数 O(logn)原理c[x]:以x结尾的长度lowbit(x)的所有数的和父节点找所有子节点(求和操作)：c[x] = a[x] + c[x-1] + ... + c[lowbit(x-1)]，x为偶数时，每一次去掉最后一个1；x为奇数时，没有子节点 子节点找父节点(修改操作)：…
2022/9/5 1:22:51 人评论 次浏览 -
树状数组学习笔记
一：树状数组定义 望文生义,树状数组就是用树形结构来模拟数组的一种数据结构。 二：图解（纯手绘，难看勿喷） 编辑 C表示从1-k的和， C[1]=a[1] C[2]=C[1]+a[2] C[3]=a[3] C[4]=C[2]+C[3]+a[4] C[5]=a[5] C[6]=C[5]+a[6] C[7]=a[7] C[8]=C[4]+C[6]+C[7]+a[8] C[9]=a…
2022/9/2 23:25:10 人评论 次浏览 -
1032 换个角度思考 树状数组 离线算法 区间有多少小于等于k的数
链接：https://ac.nowcoder.com/acm/contest/26896/1032来源：牛客网 题目描述给定一个序列，有多次询问，每次查询区间里小于等于某个数的元素的个数 即对于询问 (l,r,x)，你需要输出 ∑i=lr[ai≤x]\sum_{i=l}^{r}[a_i \le x]∑i=lr[ai≤x] 的值 其中 [exp] 是一个函…
2022/8/13 14:23:37 人评论 次浏览 -
树状数组（一）
前置知识 lowbit 求出最后一个二进制中最后一个1在什么位置 int lowbit(int x) {return x & (-x); }原理:原码 & 补码 例如：11 & (-11) 11原码: 0000 1011 -11原码: 1000 1011 -11反码: 1111 0100 -11补码: 1111 01010000 1011 & 1111 0101-----------0…
2022/8/11 6:27:08 人评论 次浏览 -
LCA在线算法（树状倍增）
对于一棵树里的任意两个节点，若他们的深度相同，显然他们到最近公共祖先的距离是相同的，我 们可以利用这个性质来求最近公共祖先。对于两个深度相同的节点，若此时父亲节点是同一个点，那么最近公共祖先就是父亲节点，如果不 是的话我们就让他们向上跳到自己的父亲节点，…
2022/7/28 1:24:03 人评论 次浏览 -
sql查询树状结构某节点下的所有子节点
with cte_child(id,areaName,pid,level)as( --起始条件 select id,areaName,pid,0 as level from erp_area where id = 1 -- 优先列出第一节点查询条件 union all --递归条件 select a.id,a.areaName,a.pid,b.level+1 from erp_area a inner…
2022/7/21 2:26:02 人评论 次浏览 -
树状数组-327. 区间和的个数
问题描述 给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。 区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。示例 1： 输入：nums = [-2,5,-…
2022/7/5 23:20:36 人评论 次浏览 -
Nodejs：（借鉴）列表数据结构，转换成树状结构
借鉴内容：列表数据结构转换成树状结构const depts = [{ "id": "1175310929766055936", "pid": "", "companyId": "1", "name": "总裁办", "code": "ZCB1", "…
2022/6/24 14:21:54 人评论 次浏览 -
算法归纳4-前缀和/差分/树状数组/线段树
1，对比https://blog.csdn.net/honghuidan/article/details/77527808 两者相同点：单点/区间修改，区间查询区间查询：前缀和 区间修改，单点查询：差分 单点修改，区间查询：树状数组，线段树 区间修改，区间查询：线段树+懒标记不同点：树状数组只能维护前缀操作和(前缀…
2022/6/7 1:20:45 人评论 次浏览 -
树状数组笔记
lowbit：保留数在2进制下最后一个1，前面全变0 模板1：单点修改，区间查询 例题：Problem - 1679C - Codeforces#include<stdio.h> #include<math.h> #include<string.h> #include<ctype.h> #include<iostream> #include<algorithm> …
2022/5/30 23:22:44 人评论 次浏览 -
二维树状数组模板（自用）
demo：1 #include<iostream>2 #include<algorithm>3 #include<cmath>4 #include<cstring>5 #include<queue>6 #include<cstdio>7 #define LL long long 8 using namespace std;9 const int maxa=1024*2+10;//~~pow(2,11)+10 10 LL n,…
2022/5/22 23:05:30 人评论 次浏览 -
LibreOJ 131 树状数组2：区间修改，单点查询
题目地址 Solution 前面已经知道了树状数组的单点修改和区间查询。这里利用差分的思想：具体来说，维护 \(b\) 数组： \[b[i] = a[i]-a[i-1] \]其中 \(a\) 为原来数组。可以发现 \[a[i] = \sum_{k=1}^ib[k] \]因此我们只需要对 \(b\) 利用树状数组维护，get_sum[i]即可得到…
2022/5/3 6:12:57 人评论 次浏览 -
优化的基于树状位压缩数组的字符集合
之前在《基于树状位压缩数组的字符集合》中介绍了一种利用位压缩数组来减少空间占用和提高集合操作效率的字符集合 CharSet。 实际测试下来，CharSet 的耗时只有 HashSet<char> 的 50%~80%，而集合操作的耗时更是只有 10%。旧文章里最后的测试结论有问题，应该是误使…
2022/4/27 6:12:46 人评论 次浏览 -
【算法模板】离线树状数组(区间查询小于等于x的数个数)
只需要把询问按x升序排序，在查询的过程中不断让树状数组把<=x元素的下标处+1即可。（为此，把序列按val排序） #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10;pair<int, int> a[N]; #define val first #define pos secondstruct…
2022/4/18 22:12:34 人评论 次浏览
